Schnelleinstieg Reader


Startseite FSU

Computational Geometry I

This is class is about geometric modeling Central to this class is the Voronoi diagram and its dual Delaunay triangulation in two and three dimensions. Voronoi diagrams and Delaunay triangulations are beautiful and mathematically rich data structures that found many applications in geometric modeling.

In the first part of the lecture we discuss how to compute Delaunay triangulations. Special emphasis will be put on low level predicates like deciding if a point is inside, outside or on the boundary of a ball. In algorithms that compute Voronoi diagrams or Delaunay triangulations such predicates have to be evaluated many times. There are different algorithms to compute Voronoi diagrams building on different geometric ideas and algorithmic paradigms. We discuss some of them.

In the second part of the lecture we use Delaunay triangulations in applications like surface reconstruction, meshing and geometric data analysis. On the left you can see an example applications in bio-geometric modeling, namly identifying caveties in macromolecules. Caveties can be potential binding sites of protein. Through the applications we discuss many more geometric and topological properties of Voronoi diagrams and Delaunay triangulations.

There is an exercise session accompanying the class. The exercises are partly of theoretical nature, but also cover implementations of the algorithms and data structures using the powerful C++ library CGAL.


Suggested reading:

  • Tamal K. Dey. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis. Cambridge University Press
  • Herbert Edelsbrunner.Geometry and Topology for Mesh Generation. Cambridge University Press
  • Afra Zomorodian. Topology for Computing. Cambridge University Press
  • Mark de Berg, Mark van Kreveld, Mark Overmars and Otfried Schwarzkopf.Computational Geometry. Springer Verlag

Please register for this class through CAJ (only for registered users).