syllabus
1. Information regarding the programme
1.1 Higher education institution 	Babes-Bolyai University Cluj-Napoca	
1.2 Faculty	Faculty of Mathematics and Computer Science	
1.3 Department	Department of Computer Science	
1.4 Field of study	Computer Science	
1.5 Study cycle	Bachelor	
1.6 Study programme / Qualification 	Computer Science	

2. Information regarding the discipline 
2.1 Name of the discipline	Computational Geometry	
2.2 Course coordinator 	Lect. Dr. Liana Topan	
2.3 Seminar coordinator	Lect. Dr. Liana Topan	
2.4. Year of study	II	2.5 Semester	4	2.6. Type of evaluation	E	2.7 Type of discipline	Elective Course	

3. Total estimated time (hours/semester of didactic activities) 
3.1 Hours per week        
3		Of which: 3.2 course
2		3.3
seminar/laboratory
1		
3.4 Total hours in the curriculum 
42		Of which: 3.5 course
28		3.6 seminar/laboratory
14		
Time allotment:	hours	
Learning using manual, course support, bibliography, course notes	20	
Additional documentation (in libraries, on electronic platforms, field documentation) 	10	
Preparation for seminars/labs, homework, papers, portfolios and essays	23	
Tutorship	10	
Evaluations	20	
Other activities: ..................	-	
3.7 Total individual study hours 	83	
3.8 Total hours per semester	125	
3.9 Number of ECTS credits	5	

4. Prerequisites (if necessary)
4.1. curriculum	•		
4.2. competencies	•	Elementary knowledge in geometry, Average programming skills	

5. Conditions (if necessary)
5.1. for the course	•		
5.2.  for the seminar /lab activities	•	Laboratory with computers	

6. Specific competencies acquired 
Professional competencies	Understanding of basic concepts of mathematics and
use them to problem-solving activities.
Ability to understand and approach problems of
modeling nature from other sciences
Ability to work independently and/or in a team in order
to solve problems in defined professional contexts.	
Transversal competencies	Ability to apply compiler techniques to different real life problems
Ability to model phenomena using formal languages

7. Objectives of the discipline (outcome of the acquired competencies)
7.1 General objective of the discipline
	Ability to understand and approach problems of
modeling nature from other sciences
	
7.2 Specific objective of the discipline
	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.	

8. Content
8.1 Course	Teaching methods	Remarks	
1.	Convex Hulls in the Plane. Degeneracies and Robustness.	Exposure: description, explanation, examples		
2.	Convex Hulls. The Constructions of Convex Hulls in the Plane 	Exposure: description, explanation, examples		
3.	Segment Intersection. The Doubly-Connected Edge List	Exposure: description, explanation, examples		
4.	Computing the Overlay of Two Subdivisions	Exposure: description, explanation, examples		
5.	The Art Gallery Problem. Triangulations	Exposure: description, explanation, examples		
6.	Partitioning a Polygon into Monotone Pieces. Triangulating a Monotone Polygon	Exposure: description, explanation, examples		
7.	Half-Plane Intersections	Exposure: description, explanation, examples		
8.	Point Location and Trapezoidal Maps	Exposure: description, explanation, examples		
9.	A Randomized Incremental Algorithm for Point Location. Dealing with Degenerate Cases	Exposure: description, explanation, examples		
10.	The Post-Office Problem. Voronoi Diagrams	Exposure: description, explanation, examples		
11.	Voronoi Diagrams of Line Segments. Farthest Point Voronoi Diagram	Exposure: description, explanation, examples		
12.	Delaunay Triangulations	Exposure: description, explanation, examples		
13.	Convex Hulls in 3-Space	Exposure: description, explanation, examples		
14.	Convex Hulls and Half-Space Intersection	Exposure: description, explanation, examples		
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
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

	
8.2 Seminar / laboratory	Teaching methods	Remarks	
1.	Implementation of Graham’s Algorithm	case studies, examples	There is one laboratory every other week	
2.	Search and Intersection	case studies, examples		
3.	Triangulations. Implementation	case studies, examples		
4.	Linear Time Triangulation. Implementation	case studies, examples		
5.	Implementation of Incremental Algorithm	case studies, examples		
6.	Algorithms for Delaunay Triangulation	case studies, examples		
7.	Implementation of Incremental Algorithm	case studies, examples		
8.				
9.				
10.				
11.				
12.				
13.				
14.				
Bibliography
The same as for courses section

	

9. Corroborating the content of the discipline with the expectations of the epistemic community, professional associations and representative employers within the field of the program

•	The course respects the IEEE and ACM Curriculla Recommendations for Computer Science studies;
•	The course exists in the studying program of all major universities in Romania and abroad;

10. Evaluation
Type of activity	10.1 Evaluation criteria	10.2 Evaluation methods	10.3 Share in the grade (%)	
10.4 Course	- know the basic principle of the domain;
- apply the course concepts
	First midterm (written)
Second midterm (written)
Final exam (written)	20%
20%
20%	
10.5 Seminar/lab activities	be able to implement course concepts and algorithms	portofolio
-continous observations	40%	
10.6 Minimum performance standards	
•	At least grade 5 (from a scale of 1 to 10) at both written exam and laboratory work.	

Date				Signature of course coordinator 	Signature of seminar coordinator
..........................		Lect. Dr. Liana Topan	            Lect. Dr. Liana Topan

Date of approval  					  Signature of the head of department	
...........................................					...........…............................