Last update: Jan. 2, 2001

BACK

BibTeX

Given a pattern of objects in continuous space, Voronoi diagrams provide a means of naturally partitioning the space into subregions. This is a rapidly expanding topic as these diagrams find application in such areas as spatial data manipulation, modelling spatial structures and spatial processes, pattern analysis and locational optimization. These areas can be found within many different scientific fields, and consequently this increases not only the use of Voronoi diagrams but also the demand for knowledge about them. This is the first book which, dealing exclusively with these diagrams, meet this demand. Material within is synthesized, unified and presented in a structured form. Emphasis of a particular perspective is deliberately avoided in order to provide a comprehensive and balanced treatment of all aspects of Volonoi diagrams. A wide range of applications drawn from over a dozen fields is discussed, enabling this book to serve as an important reference volume on this topic. This book should appeal equally to those whose interests in Voronoi diagrams are theoretical, practical or both.

Web link

Chapter 1 Introduction

• 1.1 Outline
• 1.2 History of the concept of the Voronoi diagram
  • Descartes --> Dirichlet --> Voronoi --> Delone (Delaunay)
• 1.3 Mathematical preliminaries
  • 1.3.1 Vector geometry
  • 1.3.2 Graphs
  • 1.3.3 Spatial stochastic point processes
  • 1.3.4 Efficiency of computation

Chapter 2 Definitions and Basic Properties of Voronoi Diagrams

• 2.1 Definitions of the ordinary Voronoi diagram
• 2.2 Definitions of the Delaunay tessellations (triangulation)
• 2.3 Basic properties of the Voronoi diagram
• 2.4 Basic properties of the Delaunay triangulation
• 2.5 Graphs related to the Delaunay triangulation
• 2.6 Recognition of Voronoi Diagrams
  • 2.6.1 Geometric Approach
  • 2.6.2 Combinatorial Approach

Chapter 3 Generalizations of the Voronoi Diagram

• 3.1 Weighted Voronoi diagrams
  • 3.1.1 Multiplicatively weighted Voronoi diagram
  • 3.1.2 Additively weighted Voronoi diagram
  • 3.1.3 Compoundly weighted Voronoi diagram
  • 3.1.4 Power diagram
  • 3.1.5 Sectional Voronoi diagram
  • 3.1.6 Applications
• 3.2 Higher-order Voronoi diagrams
  • 3.2.1 Order-k Voronoi diagram
  • 3.2.2 Ordered order-k Voronoi diagram
  • 3.2.3 Applications
• 3.3 Farthest-point Voronoi diagram
  • 3.3.1 Farthest-point Voronoi diagram
  • 3.3.2 kth nearest-point Voronoi diagram
  • 3.3.3 Applications
• 3.4 Voronoi diagram with obstacles
  • 3.4.1 Shortest-path Voronoi diagram
  • 3.4.2 Visibility shortest-path Voronoi diagram
  • 3.4.3 Constrained Delaunay triangulation
  • 3.4.4 SP- and VSP-Voronoi diagrams in a simple polygon
  • 3.4.5 Applications
• 3.5 Voronoi diagrams for lines
  • 3.5.1 Voronoi diagrams for a set of points, and straight line segments
  • 3.5.2 Voronoi diagrams for a set of points, straight line segments and circular arcs
  • 3.5.3 Voronoi diagrams for a set of circles
  • 3.5.4 Medial axis
  • 3.5.5 Applications
• 3.6 Voronoi diagrams for areas
  • 3.6.1 Area Voronoi diagrams
  • 3.6.2 Applications
• 3.7 Voronoi diagrams with V-distances
  • 3.7.1 Voronoi diagrams with the Minkowski metric Lp
  • 3.7.2 Voronoi diagrams with the convex distance
  • 3.7.3 Voronoi diagram with the Karlsruhe metric
  • 3.7.4 Voronoi diagram with the Hausedorff distance
  • 3.7.5 Voronoi diagram with the boat-on-a-river distance
  • 3.7.6 Voronoi diagram on a sphere
  • 3.7.7 Voronoi diagram on a cylinder
  • 3.7.8 Voronoi diagram on a cone
  • 3.7.9 Voronoi diagram on a polyhedral surface
  • 3.7.10 Miscellany
  • 3.7.11 Applications
• 3.8 Network Voronoi diagrams
  • 3.8.1 Network Voronoi node-diagram
  • 3.8.2 Network Voronoi link-diagram
  • 3.8.3 Network Voronoi are-diagram
  • 3.8.4 Applications
• 3.9 Voronoi diagrams for moving points
  • 3.9.1 Dynamic Voronoi diagrams
  • 3.9.2 Applications

Chapter 4 Algorithms for Computing Voronoi Diagrams

• 4.1 Computational preliminaries
• 4.2 Data structure for representing a Voronoi diagram
• 4.3 Incremental method
• 4.4 Divide-and-conquer method
• 4.5 Plane sweep method
• 4.6 Practical techniques for implementing the algorithms
  • 4.6.1 Inconsistency caused by numerical errors
  • 4.6.2 Construction of an error-free world
  • 4.6.3 Topology-oriented approach
• 4.7 Algorithms for higher-dimensional Voronoi diagrams
• 4.8 Algorithms for generalized Voronoi diagrams
• 4.9 Approximation algorithms

Chapter 5 Poisson Voronoi Diagrams

• 5.1 Properties of infinite Voronoi diagrams
• 5.2 Properties of Poisson Voronoi diagrams
• 5.3 Uses of Poisson Voronoi diagrams
• 5.4 Simulating Poisson Voronoi and Delaunay cells
• 5.5 Properties of Voronoi cells
  • 5.5.1 Moments of characteristics of Poisson Voronoi cells
  • 5.5.2 Conditional moments of characteristics of Poisson Voronoi cells
  • 5.5.3 Conditional moments of characteristics of the neighbouring cells of a Poisson Voronoi cell
  • 5.5.4 Distributional properties
• 5.6 Stochastic processes induced by Poisson Voronoi diagrams
  • 5.6.1 Point processes of centroids of faces
  • 5.6.2 Voronoi growth models
  • 5.6.3 Stienen model
  • 5.6.4 First-passage percolation on Poisson Voronoi diagrams and Poisson Delaunay tessellations
• 5.7 Sectional Poisson Voronoi diagrams
• 5.8 Additively weighted Poisson Voronoi diagrams: the Johnson-Mehl model
• 5.9 Higher-order Poisson Voronoi diagrams
• 5.10 Poisson Voronoi diagrams on the surface of a sphere
• 5.11 Properties of Poisson Delaunay cells
• 5.12 Other random Voronoi diagrams

Chapter 6 Spatial Interpolation

• 6.1 Polygonal methods
  • 6.1.1 Nearest neighbour interpolation
  • 6.1.2 Natural neighbour interpolation
• 6.2 Triangular methods
• 6.3 Modifying Delaunay triangulations
• 6.4 Approximating surfaces
• 6.5 Delaunay meshes for finite element methods
• 6.6 Ordering multivariate data

Chapter 7 Models of Spatial Pracesses

• 7.1 Assignment models
• 7.2 Growth models
• 7.3 Spatial-temporal processes
  • 7.3.1 Spatial competition processes: the Hotelling process
  • 7.3.2 Adjustment processes
• 7.4 Two-species models

Chapter 8 Point Pattern Analysis

• 8.1 Polygon based methods
  • 8.1.1 Direct approaches
  • 8.1.2 Indirect approaches
• 8.2 Triangle based methods
• 8.3 Nearest neighbour distance methods
  • 8.3.1 Nearest neighbour distance method for point-like objects
  • 8.3.2 Nearest neighbour distance method for point-like objects for line-like objects
  • 8.3.3 Nearest neighbour distance method for point-like objects for area-like objects
  • 8.3.4 Multi nearest neighbour point distance method
• 8.4 The shape of a point pattern
  • 8.4.1 Internal shape
  • 8.4.2 External shape
• 8.5 Spatial intensity
• 8.6 Segmenting point patterns
• 8.7 Modelling point processes

Chapter 9 Locational Optimization Through Voronoi Diagrams

• 9.1 Preliminaries
  • 9.1.1 The nonlinear nonconvex programming problem
  • 9.1.2 The descent method
  • 9.1.3 The penalty function method
• 9.2 Locational optimization of points
  • 9.2.1 Locational optimization of point-like facilities used by independent users
  • 9.2.2 Locational optimization of points in a tree-dimensional space
  • 9.2.3 Locational optimization of point-like facilities used by groups
  • 9.2.4 Locational optimization of a hierarchical facilities
  • 9.2.5 Locational optimization of observation points for estimating the total quantity of a spatial variable continuously distributed over a plane
  • 9.2.6 Locational optimization of service points of a mobile facility
  • 9.2.7 Locational optimization of terminal points through which users go to the central point
  • 9.2.8 Locational optimization of points in a continuous network
• 9.3 Locational optimization of lines
  • 9.3.1 Locational optimization of a service route
  • 9.3.2 Locational optimization of a network
  • 9.3.3 Euclidean Steiner minimum tree
• 9.4 Locational optimization over time
  • 9.4.1 Multi-stage locational optimization
  • 9.4.2 Periodic locational optimization
• 9.5 Voronoi fitting and its application to locational optimization problems
  • 9.5.1 Method for fitting a Voronoi diagram to a polygonal tessellation
  • 9.5.2 Locational optimization for minimizing restricted areas

References

Index

BACK

Page created & maintained by Frederic Leymarie, 2000-1.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu