Computational Geometry: Delaunay Triangulations and Voronoi Diagrams

Course Overview

Space decompositions are a key problem in computational geometry. The Delaunay triangulation and its dual, the Voronoi diagram, are arguably the most important decompositions studied in the field. Together, they are used by an impressive number of applications in various areas, e.g., hydrology, crystallography, biology, operations research, fluid dynamics, computer graphics, etc. The goal of this course is to present combinatorial and algorithmic results about Delaunay triangulations and Voronoi diagrams, and to highlight some interesting applications and problems. This course is part of an initiative to promote the field of Computational Geometry in Brazil and to prepare the interested public for the main event in this area, the ACM Symposium on Computational Geometry (SoCG), which will be held in Rio de Janeiro in June 2013.

Pre-Requisites

Elementary geometry
Algorithms, programming, and computational complexity

Instructor

Marcelo Siqueira
Department of Mathematics, Universidade Federal do Rio Grande do Norte, Natal, RN, Brazil

Lectures

February 18 to 22, 2013, 10:00 to 12:00, Room 224, IMPA, Rio de Janeiro, RJ, Brazil

Textbook

The main reference for this course is:

• de Berg, M.; Cheong, O.; van Kreveld, M.; Overmars, M.
  Computational Geometry: Algorithms and Applications. Springer-Verlag, 3^rd edition, 2008.

There are several complementary references that cover (entirely or partially) the contents of this course:

• Devadoss, S; O’Rourke, J.
  Discrete and Computational Geometry, Princeton University Press, 2011.
• Preparata, F. P.; Shamos, M. I.
  Computational Geometry: An Introduction, Springer-Verlag, 1985.
• Boissonnat, J-D.; Yvinec, M.
  Algorithmic Geometry, Cambridge University Press, 1995.
• Okabe, A.; Boots, B.; Sugihara, K.; Chiu, S. N.
  Spatial Tesselations: Concepts and Applications of Voronoi Diagrams, John Willey & Sons, 2^nd edition, 2000.
• de Loera, J. A.; Rambau, J.; Santos, F.
  Triangulations: Structure for Algorithms and Applications, Springer, 2010.
• Laszlo, M. J.
  Computational Geometry and Computer Graphics in C++, Prentice-Hall International, 1996.
• de Figueiredo, L. H.; Carvalho, P. C. P.
  Introdução à Geometria Computacional, 18^o Colóquio Brasileiro de Matemática, IMPA, Rio de Janeiro, Brazil, 1991.
  (in Portuguese)
• Hjelle, Ø.; Dæhlen, M.
  Triangulations and Applications, Springer, 2006.

Syllabus

Code

I wrote a simple C++ program for generating Delaunay triangulations of point sets in the Euclidean plane.

Reading List

• Leonidas Guibas, Donald E. Knuth, and Micha Sharir.
  Randomized incremental construction of Delaunay and Voronoi diagrams,
  Algorithmica, 7(1-6), p. 381-413, 1992.
• Leonidas Guibas and Jorge Stolfi.
  Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams,
  ACM Transactions on Graphics, 4(2), p. 74-123, 1985.
  (see a list of errors in this paper).
• Franz Aurenhammer.
  Voronoi diagrams: a survey of a fundamental geometric data structure.
  ACM Computing Surveys, 23(3), p. 345-405, 1991.
• Dani Lischinski.
  Incremental Delaunay Triangulation,
  Graphics Gems, Volume IV, Chapter I.5, p. 47-59, 1994 (edited by Paul Heckbert).
• Jean Gallier.
  Notes on convex sets, polytopes, polyhedra, combinatorial topology, Voronoi diagrams and Delaunay triangulations. (book in progress).

Useful Links

• Computational Geometry Pages
• Computational Geometry Bibliography Search Engine
• Computational Geometry on the Web
• The Open Problems Project
• The Voronoi Web Site
• Computational Geometry and Algorithms Library (CGAL)
• Adaptive Precision Floating-Point and Fast Robust Predicates for Computational Geometry
• Exact Geometric Computation Group (EGC group)
• Directory of Computational Geometry Software
• Geometry in Action and The Geometry Junkyard
• Applet for demonstrating Voronoi diagrams and Delaunay triangulations in 2D

Last update: February 22, 2013