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.


Elementary geometry
Algorithms, programming, and computational complexity


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


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


The main reference for this course is:

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, 2nd 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, 18o Colóquio Brasileiro de Matemática, IMPA, Rio de Janeiro, Brazil, 1991.
    (in Portuguese)
  • Hjelle, Ø.; Dæhlen, M.
    Triangulations and Applications, Springer, 2006.


Feb. 18, 2013 Voronoi diagrams: definition and basic properties PDF 1pp 3pp
Feb. 19, 2013 Voronoi diagrams: algorithms and complexity analysis PDF 1pp 3pp
Feb. 20, 2013 Delaunay triangulations: definition PDF 1pp 3pp
Feb. 21, 2013 Delaunay triangulations: basic properties PDF 1pp 3pp
Feb. 22, 2013 Delaunay triangulations: algorithms and complexity analysis PDF 1pp 3pp


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

Reading List

Useful Links

Last update: February 22, 2013