OUTLINE (cited from Chapter 1)

Introduction

On initial consideration the following problems, which concern a variety of phenomena at disparate scales, would appear to have little in common:

  • an astronomer studying the structure of the Universe;
  • an archaeologist attempting to identify the parts of a region under the influence of different neolithic clans;
  • a meteorologist estimating precipitation at a gauge which has failed to operate;
  • an urban planner locating public schools in a city;
  • a physicist studying the behaviour of liquid argon;
  • a physiologist examining capillary supply to muscle tissue.
However, these problems (all of which, together with many others, are dealt with below) can be resolved by approaches developed from a single concept which forms the subject of this book.

The concept is a simple but intuitively appealing one. Given a finite set of distinct, isolated points in a continuous space, we associate all locations in that space with the closest member of the point set. The result is a partitioning of the space into a set of regions. Figure 1.0.1 shows a simple instance for two-dimensional Euclidean space. Given its widespread occurrence it is not surprising that this concept has been discovered" many times in many different places and as a result both the diagram and its constituent regions are known by a plethora of aliases. One immediate problem we faced in writing this book was the choice of an appropriate name which would be recognized by those interested in the concept. We selected the terms Voronoi diagram and Voronoi region, which seem to be the most extensively used, although equivalent terms are identified in Section 1.2.

A second diagram can be constructed from the Voronoi diagram in m -dimensional space by joining those points whose regions share an (m-1)-dimensional face (see Figure 1.0.1). We refer to this dual diagram as the Delaunay tessellation, although it too has a number of aliases (see Section 1.2). The Delaunay tessellation may also be constructed directly from the point set by taking each (m+1)-ad of points and examining its circumsphere. If the interior of this does not contain a point of the set, we construct the simplex determined by the (m+1) points, but if it is not empty we do nothing. After all possible (m+1)-ads have been considered in this way, the result is the Delaunay tessellation.

Voronoi diagrams and Delaunay tessellations are one of a few truly interdisciplinary concepts with relevant material to be found in, but not limited to, anthropology, archaeology, astronomy, biology, cartography, chemistry, computational geometry, crystallography, ecology, forestry, geography, geology, linguistics, marketing, metallography, meteorology, operations research, physics, physiology, remote sensing, statistics, and urban and regional planning. An unfortunate consequence of this is that the material is extremely diffused, of varying mathematical sophistication and quite often idiosyncratic. The amount of material relating to Voronoi diagrams has also been growing steadily since the early 1980s as witnessed by the dominance of recent references in the Bibliography. This proliferation results in part from the opening up of new areas of application and in part from the basic concept being extended in a variety of ways (see Chapter 3). Consequently, our major motive for writing this book was to synthesize and to unify as much of the material as possible and to present it in a structured form. This seemed particularly important at the time we wrote the First Edition because no other book had appeared which was devoted exclusively to the topic. The one which came closest was Aurenhammer (1988a) (also published as Aurenhammer (1990a, 1991)) but this was a short (87 pages), highly selective survey which emphasized computational algorithms and only offered brief descriptions of applications. A number of contemporary books also provided limited treatments of Voronoi diagrams as part of more extensive coverage, for example, Ahuja and Schachter (1983), Preparata and Shamos (1985), Iri and Koshizuka (1986), and Stoyan \textit{et al.} (1987) but in most cases Voronoi diagrams accounted for less than ten percent of the books' contents. In addition, the second-last work was in Japanese which restricted its exposure to an English language audience.

While texts which devote part of their contents to Voronoi diagrams continue to be published (e.g., de Berg {\it et al.}, 1997) and others focussing on a particular kind of Voronoi diagram (e.g., Mo"ller, 1994) or a particular area of application (e.g., Agrell, 1997) are starting to appear, we believe that our text remains the only one which attempts to provide a comprehensive and balanced treatment of all aspects of Voronoi diagrams including their definition, history, computation, statistical properties and applications. It is our hope and intention that the book should appeal equally to those whose concern with Voronoi diagrams is theoretical, practical or both. However, in view of the continuing development of Voronoi diagrams, we feel that, like the First Edition, this one should be regarded as a report on the current state of affairs from a most dynamic area rather than an exhaustive study.

1.1 Outline

We have already noted that the concept of the Voronoi diagram is used extensively in a variety of disciplines and has independent roots in many of them. In Section 1.2 we begin our treatment of the Voronoi diagram by tracing its origins and that of the Delaunay tessellation from the nineteenth century up to the present. In the course of this exploration we identify the other names by which both structures are known. Before proceeding further, in order to make the book as self-contained as possible, in Section 1.3 we briefly review some basic features of several topics involved in the subsequent discussion of Voronoi diagrams. These are vector geometry, graphs, stochastic point processes, and computational efficiency.
The material in this section is not intended to be exhaustive but rather to provide a sufficient introduction for those who may be unfamiliar with such topics.

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 number of other spatial structures which are related to the Delaunay tessellation and which have been used in a variety of applications including diffusion modelling, numerical taxonomy and the exploratory display and analysis of data are described in Section 2.5. The chapter concludes by considering techniques for determining if a given structure is a Voronoi diagram and, if not, the extent to which it approximates one.

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 (Sections 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 in non-Euclidean spaces (Section 3.7), on networks (Section 3.8), and for moving points (Section 3.9). Accompanying each extension is a discussion of its applications.

In Chapter 4, after considering some computational preliminaries (Section 4.1), we examine data structures for representing the Voronoi diagram (Section 4.2). Then 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 points are located in space "at random" according to the homogeneous Poisson point process (Section 1.3.3). This diagram has been used extensively both as a descriptive and a normative model in the investigation of a wide range of empirical situations in both the natural and social sciences (Section 5.3) as diverse as galaxies, nesting territories of Royal Terns and mouthbreeder fish, and carbon particles in steels. Since the PVD is an infinite Voronoi diagram, Chapter 5 begins with a consideration of the properties of such structures (Section 5.1). We then focus on the major properties of the PVD (Section 5.2) and its constituent regions (Section 5.5), as well as those of the dual Poisson Delaunay tessellation (Section 5.11), sections of the three-dimensional PVD (Section 5.7) and generalizations of the PVD produced by weighting the points (Section 5.8), considering subsets of points rather than individual points (Section 5.9), and the PVD on the surface of a sphere (Section 5.10). We also consider stochastic processes induced by the PVD (Section 5.6) and briefly examine other types of "random" Voronoi diagrams (Section 5.12). In view of the importance of the PVD and associated Voronoi diagrams to applications, the emphasis in this chapter is on the presentation of results relating to characteristics of Voronoi regions in such structures. Although some of these are exact results derived analytically, the majority are estimates obtained from Monte Carlo simulation procedures, the different types of which are described in Section 5.4.

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 6, under the general heading of spatial interpolation, we consider how the Voronoi diagram has been used to facilitate the presentation and analysis of spatial data (values of one or more variables observed at a set of data sites in space). Such uses include employing Voronoi diagrams and Delaunay tessellations for defining various types of neighbour relationships (Section 6.1), creating meshes for finite element methods (Section 6.5), ordering multivariate data (Section 6.6), and constructing continuous surfaces from a set of data values observed at punctiform data sites (Sections 6.1-6.3), including the approximation of such surfaces (Section 6.4).

Chapter 7 considers how, by equating the procedures involved in defining the Voronoi diagram with assumptions involved in spatial processes, we may produce simple spatial models. At least four types of spatial processes, assignment (Section 7.1), growth (Section 7.2), some spatial temporal processes (Section 7.3) and spatial competition (Section 7.4) can be represented in this way. The application of such models is extensive and examples from areas as diverse as crystallography, solid state physics, biology, astronomy, physiology, archaeology and urban economics are presented.

Use of the Voronoi diagram and the Delaunay tessellation in point pattern analysis is described in Chapter 8. Section 8.1 considers different methods using the Voronoi diagram while Section 8.2 examines those methods which make use of the Delaunay tessellation. In both of these sections our concern is with how the points in a given set are positioned with respect to each other and the space in which they are located. In Section 8.3 our attention shifts to a consideration of how the members of the point set are located with respect to other objects, not members of the set, which are also located in the same space. These objects may be other points, lines or areas or a combination of all three. We also examine how Voronoi concepts can be used to describe the shape of a point pattern (Section 8.4), estimate its spatial intensity (Section 8.5), and divide it into sub-units (Section 8.6). Section 8.7 echoes Section 5.6 by considering some stochastic point processes that are induced by Voronoi diagrams.

Finally, Chapter 9 deals with the various ways in which the Voronoi diagram can be applied in solving locational optimization problems. Although problems relating to locational optimization on a network have been the subject of extensive investigation, less work has been undertaken on problems in the plane and it is such problems which are emphasized in this chapter. Planar optimization problems are important in a number of natural and social sciences. Examples range from locating observation sites for estimating a continuous spatial random variable to the location of various types of public facilities such as health clinics, fire stations and public transportation stops. All of these problems involve objects which can be represented as points and they, and other situations, form the subject matter of Section 9.2. Section 9.3 considers problems relating to the location of linear features, while Section 9.4 extends the discussion to situations where the objects under study are not located synchronously in the space. The final section (Section 9.5) illustrates how locational optimization procedures relate to fitting a Voronoi diagram to a given tessellation, a topic which is treated more generally in Section 2.6.


Back to Voronoi Diagrams