Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - în limba engleză
Limba de predare: Engleză

SYLLABUS

I. General data
Code	Subject	
MMG0006	Computational Geometry	

Semester	Hours: C+S+L	Category	Status	
4	2+1+1	speciality	optional	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
ŢOPAN Liana Manuela	Ph.D.	Lect.	Geometry	*			

Associated faculty members
Name and	Scientific	Institution	Type of	Type of activity	
surname	title		position	C	S	L	

III. Course objectives
The purpose of the course is to present an introduction in algorithmic geometry and some tools used in applied mathematics, information technology and some other scientific domains. The seminars facilitates a better understanding of the theoretical notions.	

IV. Course contents
Algorithmical foundations. Geometric search. Convex hulls. Closeness problems. The Voronoi diagram. Plane triangulations. Intersections (of convex polygons, of segment lines, of halfplanes). Delaunay triangulations.	

V. Bibliography
1. DE BERG, M. - VAN KREFELD, M. - OVERMARS, M. - SCHWARZKOPF, O.:  Computational Geometry,  (2nd edition), Springer, 2000
2. GOODMAN, J. - O'ROURKE, J. (eds.): Handbook of  Discrete and Computational Geometry, CRC Press, 1997
3. OKABE, A. - BOOTS, B. - SUGIHARA, K.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, John Wiley, 1992
4. O'ROURKE, J.: Art Gallery Theorems and Algorithms, Oxford University Press, 1987
5. O'ROURKE, J.: Computational Geometry in C, Cambridge University Press, 1994	

VI. Thematic of didactic activities per weeks
Week 1: Algorithmical foundations. Geometrical conditions. Computational models.
Week 2: Geometric search. Point location. Range searching.
Week 3: Convex hulls. The constructions of convex hulls in the plane.
Week 4: Convex hulls in higher dimensions.
Week 5: Applications in statistics.
Week 6: Closeness problems. The closest pair problem.
Week 7: The Voronoi diagram.
Week 8: Plane triangulations.
Week 9: Generalized Voronoi diagrams. Intervals and coverings.
Week 10: Plane intersections. Intersections of convex polygons. Intersections of line segments.
Week 11: Intersections os halfplanes. The kernel of a plane polygon.
Week 12: Space intersections. Intersections of convex polygons. Intersection of halfspaces.
Week 13: The geometry of rectanfles. The aria and the perimeter of a region of rectangles.
Week 14: The shape of a region of rectangles. Intersections of rectangles.	

VII. Didactic methods used
Exposition, demonstration, problematization, algorithmization, exercises.	

VIII. Assessment
There will be two partial exams during the semester. There grades will account each 20%.The students will be asked to implement some of the algorithms, which will provide another 20% of the final grade. A written final exam will also give 20%. The remaining 20% comes from the student activity in the seminar.	

IX. Additional references
1. BOISSONNAT,  J.-D. - YVINEC, M.: Algorithmic Geometry, Cambridge University Press, 1998
2. CORMEN, T.H. - LEISERSON, C.E. - RIVEST, R.L.: Introduction to Algorithms, The MIT Press, Cambridge, Massachusets, 1990
3. EDELSBRUNNER, H.: Algorithms in Combinatorial Geometry, Springer, 1997
4. PREPARATA, F.P. - SHAMOS, M.I.: Computational Geometry, Springer, 1985	

	Date,							Course responsible,
15.09.2008	Lect. ŢOPAN Liana Manuela, Ph.D.

                                                    Chair Head
                                    Prof. Univ. Dr. ANDRICA Dorin, Ph.D.