Advertisement
Published in:
2011 | OriginalPaper | Chapter
Dirichlet–Voronoi Diagrams and Delaunay Triangulations
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this chapter we present the concepts of a Voronoi diagram and of a Delaunay triangulation. These are important tools in computational geometry, and Delaunay triangulations are important in problems where it is necessary to fit 3D data using surface splines. It is usually useful to compute a good mesh for the projection of this set of data points onto the xy-plane, and a Delaunay triangulation is a good candidate. Our presentation will be rather sketchy.We are primarily interested in defining these concepts and stating their most important properties without proofs. For a comprehensive exposition of Voronoi diagrams, Delaunay triangulations, and more topics in computational geometry, our readers may consult O’Rourke [10], Preparata and Shamos [11], Boissonnat and Yvinec [2], de Berg, Van Kreveld, Overmars, and Schwarzkopf [1], or Risler [12]. The survey by Graham and Yao [7] contains a very gentle and lucid introduction to computational geometry.