Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Master
SUBJECT

Code	Subject	
MMG1007	Algorithmic Geometry	

Section	Semester	Hours: C+S+L	Category	Type	
Computational Mathematics - in Hungarian	1	2+2+0		compulsory	
Computational Mathematics - in Hungarian	1	2+2+0	speciality	compulsory	
Didactic Mathematics - in Hungarian	1	2+2+0	speciality	compulsory	
Interdisciplinary Mathematics - in Hungarian	1	2+2+0	speciality	compulsory	

Teaching Staff in Charge	Prof. VARGA Csaba Gyorgy, Ph.D., csvarga@cs.ubbcluj.ro	
Aims	The purpose of the course is to familiarize the students with the notions and methods of the Computational Geometry, which can be applied in many areas of science, such as Applied Mathematics, Physics, Biology, Computer Science. Here we remark the applications of the Voroni diagrams in Astronomy, Molecular Physics, Biology and others. The students can use these notions in research and teaching as well. At the course and seminars we put the accent on the applications.	
Content	Courses 

Course 1. Graphs
     -  elements from the theory of graphs
     - planar graphs,  Theorem of  Euler
Course 2. Line Segment Intersection
     - algorithm for computing the intersection of line segments
     - the algorithm&#8217;s complexity
Course 3.  Plane subdivison
     - Computing the overlay of two subdivisions
     - Computing the overlay of two polygons
Course 4. Triangulation of polygons
     - Art Gallery Theorem
     - decompositions of the polygons in monotone pieces
Course 5. Triangulation of monotone polygons
Course 6. Convex Sets
     - Computing the convex hull of a set (algorithms of Jarvis and Graham)
Course 7. Voronoi Diagrams
     - Voronoi Diagrams  and basic properties
     - Construction of the Voronoi Diagrams using &#8220;divide et impera&#8221; method
Course 8. Triangulation of a finite set of points 
     - computing the  Delaunay triangulation
Course 9. The geometry of casting
Course 10. Dynamic and kinetic Voronoi Diagrams
Course 11. Higher Dimensions
     - Voronoi Diagrams in higher dimensions
     - Delaunay Triangulation 
     - an application in astronomy     
Course 12. An application in Biology
     -  the plants growth using the Voronoi Diagrams 
Course 13. An application of the Voronoi Diagram in describing the protein&#8217;s structure
     -  computing the volumul of the  protein
Course 14. An application  in Physics
     - the structure of the oxygen atom
     - an application in the  Mechanics of Fluids

Seminars
  
Seminar 1. complexity of the algorithms, data structure
Seminar 2. searching trees, B-trees
Seminar 3. Triangulations of Polygons
Seminar 4. Construction of the Sigma chain in the Voronoi Diagrams
Seminar 5. Noneuclidian  metrics, Poincare model
Seminar 6. Affine diagrams, Weighted diagrams
Seminar 7. Triangle with smallest Area   
Seminar 8. Intersection of Half Planes 
Seminar 9. the structure of proteins
Seminar 10. dynamics of Fluids
Seminar 11. The galaxies distribution   
Seminar 12. the structure of the oxygen  atom
Seminar 13. presentation of  an essay  (I)
Seminar 14.  presentation of an essay (II)

Bibliography	1. CHEN JIANER, Computational Geometry: Methods and Applications, Texas A & M University, 1996. 
2. BOISSONAT, J.-D.- YVINEC, M, Algorithmic Geometry, Cambridge, 1998. 
3. T.H. COrmen, CH. E. LEISERSON, R.R. RIVEST, Introducere în algoritmi,  Ediţia în limba română Computer Libris Agora, 2000.
4. V. N. Serezhkin, V. A. Blatov, and A. P. Shevchenko. Voronoi-dirichlet  polyhedra for uranium(vi) atoms in oxygencontaining compounds. In the Russian Journal of Coordination Chemistry, volume 21, pages 155&#8211;161, 1995.
5.  M. Serrano1, G. D. Fabritiis2, P. Espaol1, E. G. Flekky3, and P. V. Coveney. Mesoscopic dynamics of voronoi fluid particles. In In the Journal of Physics A: Mathematics and General, volume 35, pages 1605&#8211;1625, 2002.
6. V. N. Serezhkin, V. A. Blatov, and A. P. Shevchenko. Voronoi-Dirichlet polyhedra for uranium(vi) atoms in oxygencontaining compounds. In the Russian Journal of Coordination Chemistry, volume 21, pages 155&#8211;161, 1995.
7. D. Stora, P.O. Agliati, M.P. Cani, F. Neyret, and J.D. Gascuel. Animating lava flows. In Graphics Interface, 1999.
9. L. Zaninetti. The galaxies distribution as given from the Voronoi diagrams. In the Journal of Astronomy and Astrophysics, Italy.
10. F. M. Richards. The interpretation of protein structures: total volume, group volume distributions, and packing density. In In the Journal of Molecular Biology, volume 82, pages 1&#8211;14, 1974.
11. W. L. Roque and H. Choset. The green island formation in forest fire modeling with Voronoi diagrams. In the 3rd  Center for Geometric Computing Workshop on Compuational Geometry, 1998.
	
Assessment	Activity on Seminars 30%
Presentation of an essay 30%
Oral final exam 40%