| |
| |
| |
| Introduction | |
| |
| |
| |
| Elementary Properties | |
| |
| |
| |
| Voronoi diagram | |
| |
| |
| |
| Delaunay triangulation | |
| |
| |
| |
| Basic Algorithms | |
| |
| |
| |
| A lower time bound | |
| |
| |
| |
| Incremental construction | |
| |
| |
| |
| Divide & conquer | |
| |
| |
| |
| Plane sweep | |
| |
| |
| |
| Lifting to 3-space | |
| |
| |
| |
| Advanced Properties | |
| |
| |
| |
| Characterization of Voronoi diagrams | |
| |
| |
| |
| Delaunay optimization properties | |
| |
| |
| |
| Generalized Sites | |
| |
| |
| |
| Line segment Voronoi diagram | |
| |
| |
| |
| Convex polygons | |
| |
| |
| |
| Straight skeletons | |
| |
| |
| |
| Constrained Delaunay and relatives | |
| |
| |
| |
| Voronoi diagrams for curved objects | |
| |
| |
| |
| Splitting the Voronoi edge graph | |
| |
| |
| |
| Medial axis algorithm | |
| |
| |
| |
| Higher Dimensions | |
| |
| |
| |
| Voronoi and Delaunay tessellations in 3-space | |
| |
| |
| |
| Structure and size | |
| |
| |
| |
| Insertion algorithm | |
| |
| |
| |
| Starting tetrahedron | |
| |
| |
| |
| Power diagrams | |
| |
| |
| |
| Basic properties | |
| |
| |
| |
| Polyhedra and convex hulls | |
| |
| |
| |
| Related diagrams | |
| |
| |
| |
| Regular simplicial complexes | |
| |
| |
| |
| Characterization | |
| |
| |
| |
| Polytope representation in weight space | |
| |
| |
| |
| Flipping and lifting cell complexes | |
| |
| |
| |
| Partitioning theorems | |
| |
| |
| |
| Least-squares clustering | |
| |
| |
| |
| Two algorithms | |
| |
| |
| |
| More applications | |
| |
| |
| |
| Higher-order Voronoi diagrams | |
| |
| |
| |
| Farthest-site diagram | |
| |
| |
| |
| Hyperplane arrangements and k-sets | |
| |
| |
| |
| Computing a single diagram | |
| |
| |
| |
| Cluster Voronoi diagrams | |
| |
| |
| |
| Medial axis in three dimensions | |
| |
| |
| |
| Approximate construction | |
| |
| |
| |
| Union of balls and weighted �-shapes | |
| |
| |
| |
| Voronoi diagram for spheres | |
| |
| |
| |
| General Spaces It Distances | |
| |
| |
| |
| Generalized spaces | |
| |
| |
| |
| Voronoi diagrams on surfaces | |
| |
| |
| |
| Specially placed sites | |
| |
| |
| |
| Convex distance functions | |
| |
| |
| |
| Convex distance Voronoi diagrams | |
| |
| |
| |
| Shape Delaunay tessellations | |
| |
| |
| |
| Situation in 3-space | |
| |
| |
| |
| Nice metrics | |
| |
| |
| |
| The concept | |
| |
| |
| |
| Very nice metrics | |
| |
| |
| |
| Weighted distance functions | |
| |
| |
| |
| Additive weights | |
| |
| |
| |
| Multiplicative weights | |
| |
| |
| |
| Modifications | |
| |
| |
| |
| Anisotropic Voronoi diagrams | |
| |
| |
| |
| Quadratic-form distances | |
| |
| |
| |
| Abstract Voronoi diagrams | |
| |
| |
| |
| Voronoi surfaces | |
| |
| |
| |
| Admissible bisector systems | |
| |
| |
| |
| Algorithms and extensions | |
| |
| |
| |
| Time distances | |
| |
| |
| |
| Weighted region problems | |
| |
| |
| |
| City Voronoi diagram | |
| |
| |
| |
| Algorithm and variants | |
| |
| |
| |
| Applications and Relatives | |
| |
| |
| |
| Distance problems | |
| |
| |
| |
| Post office problem | |
| |
| |
| |
| Nearest neighbors and the closest pair | |
| |
| |
| |
| Largest empty and smallest enclosing circle | |
| |
| |
| |
| Subgraphs of Delaunay triangulations | |
| |
| |
| |
| Minimum spanning trees and cycles | |
| |
| |
| |
| �-shapes and shape recovery | |
| |
| |
| |
| �-skeletons and relatives | |
| |
| |
| |
| Paths and spanners | |
| |
| |
| |
| Supergraphs of Delaunay triangulations | |
| |
| |
| |
| Higher-order Delaunay graphs | |
| |
| |
| |
| Witness Delaunay graphs | |
| |
| |
| |
| Geometric clustering | |
| |
| |
| |
| Partitional clustering | |
| |
| |
| |
| Hierarchical clustering | |
| |
| |
| |
| Motion planning | |
| |
| |
| |
| Retraction | |
| |
| |
| |
| Translating polygonal robots | |
| |
| |
| |
| Clearance and path length | |
| |
| |
| |
| Roadmaps and corridors | |
| |
| |
| |
| Miscellanea | |
| |
| |
| |
| Voronoi diagram of changing sites | |
| |
| |
| |
| Dynamization | |
| |
| |
| |
| Kinetic Voronoi diagrams | |
| |
| |
| |
| Voronoi region placement | |
| |
| |
| |
| Maximizing a region v | |
| |
| |
| |
| Voronoi game | |
| |
| |
| |
| Hotelling game | |
| |
| |
| |
| Separating regions | |
| |
| |
| |
| Zone diagrams and relatives | |
| |
| |
| |
| Zone diagram | |
| |
| |
| |
| Territory diagram | |
| |
| |
| |
| Root finding diagram | |
| |
| |
| |
| Centroidal Voronoi diagram | |
| |
| |
| |
| Proximity structures on graphs | |
| |
| |
| |
| Voronoi diagrams on graphs | |
| |
| |
| |
| Delaunay structures for graphs | |
| |
| |
| |
| Alternative Solutions in R<sup>d</sup> | |
| |
| |
| |
| Exponential lower size bound | |
| |
| |
| |
| Embedding into low-dimensional space | |
| |
| |
| |
| Well-separated pair decomposition | |
| |
| |
| |
| Post office revisited | |
| |
| |
| |
| Exact solutions | |
| |
| |
| |
| Approximate solutions | |
| |
| |
| |
| Abstract simplicial complexes | |
| |
| |
| |
| Conclusions | |
| |
| |
| |
| Sparsely covered topics | |
| |
| |
| |
| Implementation issues | |
| |
| |
| |
| Some open questions | |
| |
| |
| Bibliography | |
| |
| |
| Index | |