2011 | OriginalPaper | Buchkapitel
Dirichlet–Voronoi Diagrams and Delaunay Triangulations
verfasst von : Jean Gallier
Erschienen in: Geometric Methods and Applications
Verlag: Springer New York
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.