Aurenhammer F., Klein R., Lee D.-T. Voronoi Diagrams and Delaunay Triangulations

Singapore: World Scientific Publishing Company, 2013. — 345 p.Voronoi diagrams partition space according to the influence certain sites exert on their environment. Since the 17th century, such structures play an important role in many areas like Astronomy, Physics, Chemistry, Biology, Ecology, Economics, Mathematics and Computer Science. They help to describe zones of political influence, to determine the hospital nearest to an accident site, to compute collision-free paths for mobile robots, to reconstruct curves and surfaces from sample points, to refine triangular meshes, and to design location strategies for competing markets.
This unique book offers a state-of-the-art view of Voronoi diagrams and their structure, and it provides efficient algorithms towards their computation.
Readers with an entry-level background in algorithms can enjoy a guided tour of gently increasing difficulty through a fascinating area. Lecturers might find this volume a welcome source for their courses on computational geometry. Experts are offered a broader view, including many alternative solutions, and up-to-date references to the existing literature; they might benefit in their own research or application development.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
Higher Dimensions
Voronoi And Delaunay Tessellations In 3-space
Power Diagrams
Regular Simplicial Complexes
Partitioning Theorems
Higher-order Voronoi Diagrams
Medial Axis In Three Dimensions
General Spaces & Distances
Generalized Spaces
Convex Distance Functions
Nice Metrics
Weighted Distance Functions
Abstract Voronoi Diagrams
Time Distances
Applications and Relatives
Distance Problems
Subgraphs Of Delaunay Triangulations
Supergraphs Of Delaunay Triangulations
Geometric Clustering
Motion Planning
Miscellanea
Voronoi diagram of changing sites
Voronoi Region Placement
Zone Diagrams And Relatives
Proximity Structures On Graphs
Alternative Solutions in Rd
Conclusions
Sparsely Covered Topics
Implementation Issues
Some Open Questions