×

Voronoi diagrams. (English) Zbl 0995.65024

Sack, J.-R. (ed.) et al., Handbook of computational geometry. Amsterdam: North-Holland. 201-290 (2000).
From the introduction: We are trying to highlight the intrinsic potential of Voronoi diagrams, that lies in its structural properties, in the existence of efficient algorithms for its construction, and in its adaptability.
We start in Section 2 with a simple case: the Voronoi diagram and the Delaunay triangulation of \(n\) points in the plane, under the Euclidean distance. We state elementary structural properties that follow directly from the definitions. Further properties will be revealed in Section 3, where different algorithmic schemes for computing these structures are presented. In Section 4 we complete our presentation of the classical two-dimensional case, and turn to generalizations. Next, in Section 5, important geometric applications of the Voronoi diagram and the Delaunay triangulation ar discussed. Finally, Section 6 concludes the chapter and mentions some open problems.
For the entire collection see [Zbl 0930.65001].

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDFBibTeX XMLCite