Spatial tessellations: concepts and applications of Voronoi diagrams. With a foreword by D. G. Kendall.

*(English)*Zbl 0877.52010
Wiley Series in Probability and Mathematical Statistics. Chichester: Wiley. xii, 532 p. (1992).

From the introduction: “We provide a comprehensive and balanced treatment of all aspects of Voronoi diagrams including their definition, history, computation, statistical properties and applications.

In Chapter 1, Section 1.2, we begin our treatment of the Voronoi diagram by tracing its origins and that of the Delaunay tessellation (the dual diagram of the Voronoi diagram) from the nineteenth century up to the present.

Chapter 2 begins with a formal definition of both the Voronoi diagram (Section 2.1) and the Delaunay tessellation (Section 2.2). Sections 2.3 and 2.4 present properties of both structures, most of which are exploited in applications described elsewhere in the book.

A major reason for the continuing success of the Voronoi diagram is that it can be generalized in a variety of ways. Such generalizations are the subject of Chapter 3 and include weighting the points in various ways (Section 3.1), considering regions associated with subsets of points rather than individual points (Section 3.2 and 3.3), including obstacles in the space (Section 3.4), considering regions associated with sets of geometric features other than points (Sections 3.5 and 3.6), examining Voronoi diagrams involving non-Euclidean distances (Section 3.7) and on networks (Section 3.8).

In Chapter 4, after an initial consideration of data structures for representing the Voronoi diagram (Section 4.2), we present major algorithms for constructing it (sections 4.3-4.5). For application purposes it is necessary to be able to implement these algorithms, and in Section 4.6 we consider various practical techniques for doing this. Up to this point in the chapter the discussion concentrates on the planar Voronoi diagram, but in Section 4.7 we consider Voronoi diagrams in higher dimensions and in Sections 4.8 and 4.9 we examine algorithms for generating the various generalized diagrams introduced in Chapter 3.

The Poisson Voronoi diagram (PVD) refers to the situation in which the points are located in space ‘at random’ according to the homogeneous Poisson point process. Chapter 5 presents the major properties of the PVD (Section 5.1) and its constituent regions (Section 5.4) as well as those of the dual Poisson Delaunay tessellation (Section 5.9), sections of the three-dimensional PVD (Section 5.5) and generalizations of the PVD produced by weighting the points (Section 5.6), considering subsets of points rather than individual points (Section 5.7) and the PVD on the surface of a sphere (Section 5.8). We also consider briefly other types of ‘random’ Voronoi diagrams (Section 5.10).

In the remaining chapters the emphasis shifts towards applications of Voronoi diagrams. We identify four major areas, spatial interpolation, models of spatial processes, point pattern analysis and locational optimization, each of which is the subject of a separate chapter”.

In Chapter 1, Section 1.2, we begin our treatment of the Voronoi diagram by tracing its origins and that of the Delaunay tessellation (the dual diagram of the Voronoi diagram) from the nineteenth century up to the present.

Chapter 2 begins with a formal definition of both the Voronoi diagram (Section 2.1) and the Delaunay tessellation (Section 2.2). Sections 2.3 and 2.4 present properties of both structures, most of which are exploited in applications described elsewhere in the book.

A major reason for the continuing success of the Voronoi diagram is that it can be generalized in a variety of ways. Such generalizations are the subject of Chapter 3 and include weighting the points in various ways (Section 3.1), considering regions associated with subsets of points rather than individual points (Section 3.2 and 3.3), including obstacles in the space (Section 3.4), considering regions associated with sets of geometric features other than points (Sections 3.5 and 3.6), examining Voronoi diagrams involving non-Euclidean distances (Section 3.7) and on networks (Section 3.8).

In Chapter 4, after an initial consideration of data structures for representing the Voronoi diagram (Section 4.2), we present major algorithms for constructing it (sections 4.3-4.5). For application purposes it is necessary to be able to implement these algorithms, and in Section 4.6 we consider various practical techniques for doing this. Up to this point in the chapter the discussion concentrates on the planar Voronoi diagram, but in Section 4.7 we consider Voronoi diagrams in higher dimensions and in Sections 4.8 and 4.9 we examine algorithms for generating the various generalized diagrams introduced in Chapter 3.

The Poisson Voronoi diagram (PVD) refers to the situation in which the points are located in space ‘at random’ according to the homogeneous Poisson point process. Chapter 5 presents the major properties of the PVD (Section 5.1) and its constituent regions (Section 5.4) as well as those of the dual Poisson Delaunay tessellation (Section 5.9), sections of the three-dimensional PVD (Section 5.5) and generalizations of the PVD produced by weighting the points (Section 5.6), considering subsets of points rather than individual points (Section 5.7) and the PVD on the surface of a sphere (Section 5.8). We also consider briefly other types of ‘random’ Voronoi diagrams (Section 5.10).

In the remaining chapters the emphasis shifts towards applications of Voronoi diagrams. We identify four major areas, spatial interpolation, models of spatial processes, point pattern analysis and locational optimization, each of which is the subject of a separate chapter”.

##### MSC:

52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |

52B55 | Computational aspects related to convexity |

52-02 | Research exposition (monographs, survey articles) pertaining to convex and discrete geometry |

52B12 | Special polytopes (linear programming, centrally symmetric, etc.) |

68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |

68W10 | Parallel algorithms in computer science |

68-02 | Research exposition (monographs, survey articles) pertaining to computer science |