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+0+1	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 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 labs facilitate 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. Algorithms and Applications, (3rd edition), Springer, 2008
2. CHEN, J. - Computational geometry. Methods and applications, Texas AM, 1996
3. MOUNT, D., Lectures in Computational Geometry, 1997
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: Convex Hulls in the Plane. Degeneracies and Robustness. [1 (sections 1.1, 1.2), 2 (3.1)]
Week 2: Convex Hulls. The Constructions of Convex Hulls in the Plane. [1 (chap.1), 2(4.2, 5.1), 
         3(lectures 2, 3)]
    Lab 1: Implementation of Graham’s Algorithm [5 (chap 3)]
Week 3: Line Segment Intersection. The Doubly-Connected Edge List. [1(2.1, 2.2), 3 (lecture 4),  
         2(3.3, 4.1)] 
Week 4: Computing the Overlay of Two Subdivisions. [1 (2.3), 3(lecture 5)] 
    Lab 2: Search and Intersection[5(chap 1, 7)]
Week 5: The Art Gallery Problem. Triangulations. [1 (3.1), 3(lecture 6)]
Week 6: Partitioning a Polygon into Monotone Pieces. Triangulating a Monotone Polygon. [1 (3.2,   
         3.3), 2(4.4), 3(lecture 7)]

    Lab 3: Triangulations. Implementation [5(chap 1)]
Week 7: Half-Plane Intersections. [1 (4.1, 4.2, 4.3, 4.4), 3(lecture 8)]
Week 8: Point Location and Trapezoidal Maps. [1 (6.1), 3(lecture 14)]

    Lab 4: Linear Time Triangulation. Implementation [5(chap 2)]

Week 9: A Randomized Incremental Algorithm for Point Location. Dealing with Degenerate Cases. [1    
         (6.2, 6.3), 3(lecture 15)]

Week 10: The Post-Office Problem. Voronoi Diagrams. [1 (7.1, 7.2), 2(5.2, 5.3), 3(lecture 18)]
    Lab 5: Implementation of Incremental Algorithm [5(chap 5)]
Week 11: Voronoi Diagrams of Line Segments. Farthest Point Voronoi Diagram. [1 (7.3, 7.4), 2(4.3)]
Week 12: Delaunay Triangulations. [1 (9.1, 9.2, 9.3), 3(lecture 20)] 
    Lab 6: Algorithms for Delaunay Triangulation [5(chap 5)]
Week 13: Convex Hulls in 3-Space. [1 (11.1, 11.2), 2(10.2)]

Week 14: Convex Hulls and Half-Space Intersection. [1 (11.4), 2(10.3)]

    Lab 7: Implementation of Incremental Algorithm [5(chap 5)].	

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 40% of the final grade. A final oral exam will also give 20%. 	

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	

       Dean,							Chair Head,
	Prof. dr. Leon Tambulea				Conf. Dr.  BREAZ Simion Sorin

	Date,							Course responsible,
	30.09.2009						Lect. TOPAN Liana Manuela