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

SUBJECT

Code
Subject
MMG0006 Computational Geometry
Section
Semester
Hours: C+S+L
Category
Type
Computer Science - in Romanian
Computer Science - in Hungarian
Computer Science - in English
Computer Science - in Hungarian, Miercurea Ciuc
4
2+0+1
speciality
optional
Information engineering - in English
Information engineering - in Hungarian
Information engineering - in Romanian
4
2+0+1
complementary
optional
Teaching Staff in Charge
Asist. ROTH Agoston Istvan, Ph.D.,  agoston.rothmath.ubbcluj.ro
Assoc.Prof. BLAGA Paul Aurel, Ph.D.,  pablagacs.ubbcluj.ro
Lect. TOPAN Liana Manuela, Ph.D.,  ltopanmath.ubbcluj.ro
Lect. OLAH-GAL Robert, Ph.D.,  robert.olah-galcs.ubbcluj.ro
Aims
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.
Content
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
References
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
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.
Links: Syllabus for all subjects
Romanian version for this subject
Rtf format for this subject