"Babes-Bolyai" University of Cluj-Napoca
Faculty of Mathematics and Computer Science

Computational geometry
Code
Semes-
ter
Hours: C+S+L
Credits
Type
Section
MG008
4
2+1+0
5
optional
Informatică
Teaching Staff in Charge
Lect. BLAGA Paul Aurel, Ph.D., pablaga@cs.ubbcluj.ro
Lect. SOOS Anna, Ph.D., asoos@math.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. F.P. Preparata, M.I. Shamos - Computational Geometry, Springer, 1985
2. J. O'Rourke - Computational Geometry in C, Cambridge, 1993
3. M. de Berg - Computational Geometry, Springer, 1997
Assessment
Exam.