- 1.1 Outline
- 1.2 History of the concept of the Voronoi diagram
- 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

- 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

- 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.7.1 Voronoi diagrams with the Minkowski metric
- 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

- 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

- 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

- 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

- 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

- 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

- 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

Index

Back to Voronoi Diagrams