Division of Geometry

Computational Geometry

Code: 2-MPG-203

Continuous assessment: Written assignments and projects

Final assessment: Examination

Objective: Familiarisation with the fundamental problems of computational geometry and their efficient solutions.

Course syllabus:
  1. Selected basic data structures of computational geometry.
  2. Geometric searching.
  3. Construction of the convex hull of a finite set of points.
  4. Selected proximity problems.
  5. Triangulations.
  6. Intersections of polygons and polyhedra.

Literature:

Preparata, F., Shamos, I.: Computational Geometry: An Introduction, Springer 1985.
Okabe, A. et al.: Spatial Tessellations Concepts and Applications of Voronoi Diagrams, John Wiley & Sons, 1992.
Boissonnat, J. D., Yvinec, M.: Algorithmic Geometry, 1998.
Chalmovianský, Ferko, Galbavý, Niepel: Complexity of Geometric Algorithms, UK Press, 2001.