Chapter 8 Dirichlet–Voronoi Diagrams and
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 m...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Text |
| Language: | English |
| Subjects: | |
| Online Access: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.220.77 http://www.cis.upenn.edu/~cis610/convex8.pdf |
| Summary: | 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 of Voronoi diagrams and Delaunay triangulations is far from thorough. We are primarily interested in defining these concepts and stating their most important properties. For a comprehensive exposition of Voronoi diagrams, Delaunay triangulations, and more topics in computational geometry, our readers may consult O’Rourke [31], Preparata and Shamos [32], Boissonnat and Yvinec [8], de Berg, Van Kreveld, Overmars, and Schwarzkopf [5], or Risler [33]. The survey by Graham and Yao [23] contains a very gentle and lucid introduction to computational geometry. In Section 8.6 (which relies on Section 8.5), we show that the Delaunay triangulation of a set of points, P, is the stereographic projection of the convex hull of the set of points obtained by mapping the points in P onto the sphere using inverse stereogrgaphic projection. We also prove that the Voronoi diagram of P is obtained by taking the polar dual of the above convex hull and projecting it from the north pole (back onto the hyperplane containing P). A rigorous proof of this second fact is not trivial because the central projection from the north pole is only a partial map. To give a rigorous proof, we have to use projective completions. But then, we need to define what is a convex polyhedron in projective space and for this, we use the results of Chapter 5 (especially, Section 5.2). Some practical applications of Voronoi diagrams and Delaunay triangulations are briefly discussed in Section 8.7. Let E be a Euclidean space of finite dimension, that is, an affine space E whose underlying |
|---|