Voronoi Diagrams And Delaunay Triangulations

by Franz Aurenhammer, Rolf Klein, Der-tsai Lee

Overview

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.

Product Details

ISBN-13:	9789814447638
Publisher:	World Scientific Publishing Company, Incorporated
Publication date:	08/28/2013
Pages:	348
Product dimensions:	5.90(w) x 9.10(h) x 0.90(d)

Table of Contents

1 Introduction 1

2 Elementary Properties 7

2.1 Voronoi diagram 7

2.2 Delaunay triangulation 11

3 Basic Algorithms 15

3.1 A lower time bound 16

3.2 Incremental construction 18

3.3 Divide & conquer 24

3.4 Plane sweep 28

3.5 Lifting to 3-space 31

4 Advanced Properties 35

4.1 Characterization of Voronoi diagrams 35

4.2 Delaunay optimization properties 41

5 Generalized Sites 47

5.1 Line segment Voronoi diagram 47

5.2 Convex polygons 53

5.3 Straight skeletons 54

5.4 Constrained Delaunay and relatives 62

5.5 Voronoi diagrams for curved objects 66

5.5.1 Splitting the Voronoi edge graph 67

5.5.2 Medial axis algorithm 70

6 Higher Dimensions 75

6.1 Voronoi and Delaunay tessellations in 3-space 75

6.1.1 Structure and size 75

6.1.2 Insertion algorithm 77

6.1.3 Starting tetrahedron 79

6.2 Power diagrams 81

6.2.1 Basic properties 81

6.2.2 Polyhedra and convex hulls 83

6.2.3 Related diagrams 85

6.3 Regular simplicial complexes 87

6.3.1 Characterization 88

6.3.2 Polytope representation in weight space 89

6.3.3 Flipping and lifting cell complexes 90

6.4 Partitioning theorems 93

6.4.1 Least-squares clustering 94

6.4.2 Two algorithms 97

6.4.3 More applications 100

6.5 Higher-order Voronoi diagrams 103

6.5.1 Farthest-site diagram 103

6.5.2 Hyperplane arrangements and k-sets 106

6.5.3 Computing a single diagram 109

6.5.4 Cluster Voronoi diagrams 112

6.6 Medial axis in three dimensions 114

6.6.1 Approximate construction 114

6.6.2 Union of balls and weighted α-shapes 117

6.6.3 Voronoi diagram for spheres 120

7 General Spaces It Distances 123

7.1 Generalized spaces 123

7.1.1 Voronoi diagrams on surfaces 123

7.1.2 Specially placed sites 128

7.2 Convex distance functions 129

7.2.1 Convex distance Voronoi diagrams 130

7.2.2 Shape Delaunay tessellations 136

7.2.3 Situation in 3-space 141

7.3 Nice metrics 144

7.3.1 The concept 144

7.3.2 Very nice metrics 148

7.4 Weighted distance functions 152

7.4.1 Additive weights 152

7.4.2 Multiplicative weights 156

7.4.3 Modifications 160

7.4.4 Anisotropic Voronoi diagrams 163

7.4.5 Quadratic-form distances 165

7.5 Abstract Voronoi diagrams 167

7.5.1 Voronoi surfaces 167

7.5.2 Admissible bisector systems 168

7.5.3 Algorithms and extensions 172

7.6 Time distances 175

7.6.1 Weighted region problems 175

7.6.2 City Voronoi diagram 176

7.6.3 Algorithm and variants 180

8 Applications and Relatives 183

8.1 Distance problems 183

8.1.1 Post office problem 183

8.1.2 Nearest neighbors and the closest pair 186

8.1.3 Largest empty and smallest enclosing circle 189

8.2 Subgraphs of Delaunay triangulations 194

8.2.1 Minimum spanning trees and cycles 195

8.2.2 α-shapes and shape recovery 200

8.2.3 β-skeletons and relatives 202

8.2.4 Paths and spanners 205

8.3 Supergraphs of Delaunay triangulations 207

8.3.1 Higher-order Delaunay graphs 207

8.3.2 Witness Delaunay graphs 210

8.4 Geometric clustering 211

8.4.1 Partitional clustering 212

8.4.2 Hierarchical clustering 214

8.5 Motion planning 216

8.5.1 Retraction 217

8.5.2 Translating polygonal robots 219

8.5.3 Clearance and path length 220

8.5.4 Roadmaps and corridors 222

9 Miscellanea 225

9.1 Voronoi diagram of changing sites 225

9.1.1 Dynamization 225

9.1.2 Kinetic Voronoi diagrams 226

9.2 Voronoi region placement 228

9.2.1 Maximizing a region v 229

9.2.2 Voronoi game 232

9.2.3 Hotelling game 235

9.2.4 Separating regions 236

9.3 Zone diagrams and relatives 238

9.3.1 Zone diagram 238

9.3.2 Territory diagram 241

9.3.3 Root finding diagram 242

9.3.4 Centroidal Voronoi diagram 244

9.4 Proximity structures on graphs 246

9.4.1 Voronoi diagrams on graphs 246

9.4.2 Delaunay structures for graphs 248

10 Alternative Solutions in R^d 251

10.1 Exponential lower size bound 251

10.2 Embedding into low-dimensional space 252

10.3 Well-separated pair decomposition 254

10.4 Post office revisited 258

10.4.1 Exact solutions 258

10.4.2 Approximate solutions 259

10.5 Abstract simplicial complexes 261

11 Conclusions 267

11.1 Sparsely covered topics 267

11.2 Implementation issues 269

11.3 Some open questions 272

Bibliography 275

Index 329