Spatial Tessellations Concepts and Applications of Voronoi Diagrams

by Okabe, Atsuyuki; Boots, Barry; Sugihara, Kokichi; Chiu, Sung Nok

• ISBN13: 9780471986355
• ISBN10: 0471986356
• Edition: 2nd
• Format: Hardcover
• Copyright: 2000-07-26
• Publisher: WILEY

Summary

Spatial data analysis is a fast growing area and Voronoi diagrams provide a means of naturally partitioning space into subregions to facilitate spatial data manipulation, modelling of spatial structures, pattern recognition and locational optimization. With such versatility, the Voronoi diagram and its relative, the Delaunay triangulation, provide valuable tools for the analysis of spatial data. This is a rapidly growing research area and in this fully updated second edition the authors provide an up-to-date and comprehensive unification of all the previous literature on the subject of Voronoi diagrams. Features: 'ˆ— Expands on the highly acclaimed first edition 'ˆ— Provides an up-to-date and comprehensive survey of the existing literature on Voronoi diagrams 'ˆ— Includes a useful compendium of applications 'ˆ— Contains an extensive bibliography A wide range of applications is discussed, enabling this book to serve as an important reference volume on this topic. The text will appeal to students and researchers studying spatial data in a number of areas, in particular, applied probability, computational geometry, and Geographic Information Science (GIS). This book will appeal equally to those whose interests in Voronoi diagrams are theoretical, practical or both.

Author Biography

Atsuyuki Okabe is the author of Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd Edition, published by Wiley. Barry Boots is the author of Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd Edition, published by Wiley.

Table of Contents

Foreword to the First Edition	xi
Preface to the Second Edition	xiii
Acknowledgements (First Edition)	xv
Acknowledgements (Second Edition)	xvi
Introduction	1	(42)
Outline	3	(3)
History of the concept of the Voronoi diagram	6	(6)
Mathematical preliminaries	12	(31)
Vector geometry	12	(12)
Graphs	24	(7)
Spatial stochastic point processes	31	(10)
Efficiency of computation	41	(2)
Definitions and Basic Properties of Voronoi Diagrams	43	(70)
Definitions of the ordinary Voronoi diagram	43	(9)
Definitions of the Delaunay tessellation (triangulation)	52	(5)
Basic properties of the Voronoi diagram	57	(13)
Basic properties of the Delaunay triangulation	70	(27)
Graphs related to the Delaunay triangulation	97	(6)
Recognition of Voronoi diagrams	103	(10)
The geometric approach	104	(2)
The combinatorial approach	106	(7)
Generalizations of the Voronoi diagram	113	(116)
Weighted Voronoi diagrams	119	(15)
The multiplicatively weighted Voronoi diagram	120	(3)
The additively weighted Voronoi diagram	123	(4)
The compoundly weighted Voronoi diagram	127	(1)
The power diagram	128	(3)
The sectional Voronoi diagram	131	(2)
Applications	133	(1)
Higher-order Voronoi diagrams	134	(17)
The order-k Voronoi diagram	135	(9)
The ordered order-k Voronoi diagram	144	(6)
Applications	150	(1)
The farthest-point Voronoi diagram and the kth nearest-point Voronoi diagram	151	(7)
The farthest-point Voronoi diagram	151	(4)
The kth nearest-point Voronoi diagram	155	(2)
Applications	157	(1)
Voronoi diagrams with obstacles	158	(11)
The shortest-path Voronoi diagram	158	(5)
The visibility shortest-path Voronoi diagram	163	(2)
The constrained Delaunay triangulation	165	(3)
SP-and VSP-Voronoi diagrams in a simple polygon	168	(1)
Applications	168	(1)
Voronoi diagrams for lines	169	(17)
Voronoi diagrams for a set of points and straight line segments	171	(5)
Voronoi diagrams for a set of points, straight line segments and circular arcs	176	(2)
Voronoi diagrams for a set of circles	178	(3)
Medial axis	181	(3)
Applications	184	(2)
Voronoi diagrams for areas	186	(3)
The area Voronoi diagram	186	(2)
Applications	188	(1)
Voronoi diagrams with V-distances	189	(29)
Voronoi diagrams with the Minkowski metric Lp	189	(5)
Voronoi diagrams with the convex distance	194	(7)
Voronoi diagrams with the Karlsruhe metric	201	(1)
Voronoi diagrams with the Hausdorff distance	202	(2)
Voronoi diagram with the boat-on-a-river distance	204	(2)
Voronoi diagrams on a sphere	206	(3)
Voronoi diagrams on a cylinder	209	(1)
Voronoi diagrams on a cone	210	(1)
Voronoi diagrams on a polyhedral surface	211	(1)
Miscellany	212	(3)
Applications	215	(3)
Network Voronoi diagrams	218	(6)
The network Voronoi node diagram	219	(1)
The network Voronoi link diagram	220	(1)
The network Voronoi area diagram	221	(3)
Applications	224	(1)
Voronoi diagrams for moving points	224	(5)
Dynamic Voronoi diagrams	224	(3)
Applications	227	(2)
Algorithms for Computing Voronoi Diagrams	229	(62)
Computational preliminaries	229	(6)
Data structure for representing a Voronoi diagram	235	(7)
The incremental method	242	(9)
The divide-and-conquer method	251	(6)
The plane sweep method	257	(7)
Practical techniques for implementing the algorithms	264	(11)
Inconsistency caused by numerical errors	264	(1)
Construction of an error-free world	265	(4)
Topology-oriented approach	269	(6)
Algorithms for higher-dimensional Voronoi diagrams	275	(5)
Algorithms for generalized Voronoi diagrams	280	(7)
Approximation algorithms	287	(4)
Poisson Voronoi Diagrams	291	(120)
Properties of infinite Voronoi diagrams	295	(4)
Properties of Poisson Voronoi diagrams	299	(1)
Uses of Poisson Voronoi diagrams	300	(6)
Simulating Poisson Voronoi and Delaunay cells	306	(5)
Properties of Poisson Voronoi cells	311	(39)
Moments of the characteristics of Poisson Voronoi cells	311	(4)
Conditional moments of the characteristics of Poisson Voronoi cells	315	(9)
Conditional moments of the characteristics of the neighbouring cells of a Poisson Voronoi cell	324	(7)
Distributional properties	331	(19)
Stochastic processes induced by Poisson Voronoi diagrams	350	(13)
Point processes of centroids of faces	350	(7)
Voronoi growth models	357	(3)
The Stienen model	360	(1)
Percolation on Poisson Voronoi diagrams and Poisson Delaunay tessellations	361	(2)
Sectional Voronoi diagrams	363	(11)
Additively weighted Poisson Voronoi diagrams: the Johnson--Mehl model	374	(11)
Higher order Poisson Voronoi diagrams	385	(4)
Poisson Voronoi diagrams on the surface of a sphere	389	(1)
Properties of Poisson Delaunay cells	389	(15)
Other random Voronoi diagrams	404	(7)
Spatial Interpolation	411	(42)
Polygonal methods	416	(11)
Nearest neighbour interpolation	417	(1)
Natural neighbour interpolation	418	(9)
Triangular methods	427	(7)
Modifying Delaunay triangulations	434	(3)
Approximating surfaces	437	(2)
Delaunay meshes for finite element methods	439	(7)
Two-dimensional Delaunay meshes	440	(2)
Three-dimensional Delaunay meshes	442	(4)
Ordering multivariate data	446	(7)
Models of Spatial Processes	453	(42)
Assignment models	454	(22)
Growth models	476	(6)
Spatial-temporal processes	482	(9)
Spatial competition models: the Hotelling process	482	(7)
Adjustment models	489	(2)
Two-species models	491	(4)
Point Pattern Analysis	495	(36)
Polygon-based methods	498	(8)
Direct approach	498	(4)
Indirect approaches	502	(4)
Triangle-based methods	506	(6)
Nearest neighbour distance methods	512	(9)
Nearest neighbour distance method for point-like objects	514	(3)
Nearest neighbour distance method for line-like objects	517	(3)
Nearest neighbour distance method for area-like objects	520	(1)
Multi nearest neighbour distance method	521	(1)
The shape of a point pattern	521	(4)
Internal shape	521	(2)
External shape	523	(2)
Spatial intensity	525	(2)
Segmenting point patterns	527	(2)
Modelling point processes	529	(2)
Locational Optimization Through Voronoi Diagrams	531	(54)
Preliminaries	532	(9)
The non-linear, non-convex programming problem	532	(2)
The descent method	534	(4)
The penalty function method	538	(3)
Locational optimization of points	541	(23)
Locational optimization of point-like facilities used by independent users	542	(6)
Locational optimization of points in a three-dimensional space	548	(1)
Locational optimization of point-like facilities used by groups	549	(2)
Locational optimization of a hierarchical facility	551	(4)
Locational optimization of observation points for estimating the total quantity of a spatial variable continuously distributed over a plane	555	(3)
Locational optimization of service points of a mobile facility	558	(1)
Locational optimization of terminal points through which users go to the central point	559	(4)
Locational optimization of points on a continuous network	563	(1)
Locational optimization of lines	564	(11)
Locational optimization of a service route	564	(3)
Locational optimization of a network	567	(3)
Euclidean Steiner minimum tree	570	(5)
Locational optimization over time	575	(6)
Multi-stage locational optimization	575	(3)
Periodic locational optimization	578	(3)
Voronoi fitting and its application to locational optimization problems	581	(4)
Method of fitting a Voronoi diagram to a polygonal tessellation	581	(3)
Locational optimization for minimizing restricted areas	584	(1)
References	585	(72)
Index	657