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+P	Category	Status	
4	2+0+1+0	speciality	optional	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
TOPAN Liana Manuela	Ph.D.	Lect.	Algebra, Mathematical Analysis and Geometry	*			

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

III. Course objectives
The main purpose of the course is the introduction in computational geometry, an important subject for many topics in present applied mathematics and computer science. The seminars gives some impletations by examples, exercices and problems for the results given in the course.	

IV. Course contents
1. Foundations.
1.1. Algoritmical foundations.
1.2. Geometrical conditions.
1.3. Computational models.
2. Geometric search.
2.1. Point location.
2.2. Range searching.
3. Convex hulls.
3.1. The constructions of convex hulls in the plane.
3.2. Convex hulls in higher dimensions.
4. Closeness problems.
4.1. The closest pair problem.
4.2. The Voronoi diagram.
4.3. Plane triangulations.
5. Intersections
5.1. Intersections of convex polygons.
5.2. Intersections of line segments.
5.3. Intersections of halfplanes.
5.4. The kernel of a plane polygon.
6. Delaunay triangulations	

V. Bibliography
1. DE BERG, M. - VAN KREFELD, M. - OVERMARS, M. - SCHWARZKOPF, O.:  Computational Geometry,  (2nd edition), Springer, 2000
2. BOISSONNAT,  J.-D. - YVINEC, M.: Algorithmic Geometry, Cambridge University Press, 1998
3. CORMEN, T.H. - LEISERSON, C.E. - RIVEST, R.L.: Introduction to Algorithms, The MIT Press, Cambridge, Massachusets, 1990
4. EDELSBRUNNER, H.: Algorithms in Combinatorial Geometry, Springer, 1997
5. GOODMAN, J. - O'ROURKE, J. (eds.): Handbook of  Discrete and Computational Geometry, CRC Press, 1997
6. OKABE, A. - BOOTS, B. - SUGIHARA, K.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, John Wiley, 1992
7. O'ROURKE, J.: Art Gallery Theorems and Algorithms, Oxford University Press, 1987
8. O'ROURKE, J.: Computational Geometry in C, Cambridge University Press, 1994
9. PREPARATA, F.P. - SHAMOS, M.I.: Computational Geometry, Springer, 1985

VI. Thematic of didactic activities per weeks

VII. Didactic methods used

VIII. Assessment
There will be given several written tests during the semester and the students will be asked to implement some of the algorithms. There will be an exam at the end of the semester, and the current activity will be taken into account.	

IX. Additional references

	Dean,							Chair head,

	Date,							Course responsible,
								Lect. TOPAN Liana Manuela, Ph.D.