Chapter 6: Voronoi Diagrams

Overview

For a given set of sites inside an area, the Voronoi diagram is a partition of the area into regions of the same neighborship. The Voronoi diagram is used for solving numerous problems in many fields of science. In the 2D Euclidean plane the Voronoi diagram is represented by a planar graph that divides the plane into cells .

We will concentrate on applications to geometric problems in 2D and 3D. An overview of the Voronoi diagram and its graph theoretic dual, the Delaunay triangulation or Delaunay tesselation, is presented in the surveys [Aurenhammer 91], [Bernal 92], [Fortune 92b], [Aurenhammer and Klein 00], and [Okabe et al. 92]. Additionally, Chapters 5 and 6 of [Preparata and Shamos 90] and Chapter 13 of [Edelsbrunner 87] could be considered .

We start in Section 6.1 with the simple case of the Voronoi diagram and the Delaunay triangulation of n points in the plane, under the Euclidean distance. Additionally, we will mention some of the elementary structural properties that follow from the definitions.

In Section 6.2, different algorithmic schemes for computing the structures are mentioned. We present a simple incremental construction approach which can be easily generalized to 3D; see Section 6.3.1.

We present generalizations of the Voronoi diagram and the Delaunay triangulation in Section 6.3. In Section 6.3.1, transformations to three dimensions are given, and in Section 6.3.2 the concept of constrained Voronoi diagram s is introduced. A collection of other interesting generalizations is presented in Section 6.3.3.

In Section 6.4, applications of the Voronoi diagram and the Delaunay triangulation in 2D and 3D are shown. First, in Section 6.4.1 we discuss the famous post office problem and present data structures for the nearest neighbor search based on the Voronoi diagram. Finally, in Section 6.4.2, a collection of applications is shown.

The presented pseudocode algorithms make use of straightforward and self-explanatory operations, for example, for list and array manipulations. They should be clear from the context.