Concrete and Abstract Voronoi Diagrams

Front Cover
Springer Science & Business Media, Dec 20, 1989 - Computers - 167 pages
The Voronoi diagram of a set of sites is a partition of the plane into regions, one to each site, such that the region of each site contains all points of the plane that are closer to this site than to the other ones. Such partitions are of great importance to computer science and many other fields. The challenge is to compute Voronoi diagrams quickly. The problem is that their structure depends on the notion of distance and the sort of site. In this book the author proposes a unifying approach by introducing abstract Voronoi diagrams. These are based on the concept of bisecting curves, which are required to have some simple properties that are actually possessed by most bisectors of concrete Voronoi diagrams. Abstract Voronoi diagrams can be computed efficiently and there exists a worst-case efficient algorithm of divide-and-conquer type that applies to all abstract Voronoi diagrams satisfying a certain constraint. The author shows that this constraint is fulfilled by the concrete diagrams based on large classes of metrics in the plane.
 

What people are saying - Write a review

User Review - Flag as inappropriate

aswwwed

Selected pages

Contents

Voronoi diagrams in nice metrics
9
12 Nice metrics
16
Abstract Voronoi diagrams
31
21 Definitions
32
22 Elementary properties
34
23 The neighborhoods of points in VS
36
24 Augmented curve systems
43
25 The shape of the Voronoi regions
46
34 The nondegenerate case
77
342 Finding the continuing segment
92
343 The complete algorithm
97
35 The degenerate case
99
351 Local separation of curves
101
352 Crosspoints
109
353 The modified algorithm
112
Acyclic partitions
131

26 The graph structure of abstract Voronoi diagrams
51
27 Characterizing Voronoi diagrams
52
Computing abstract Voronoi diagrams
63
31 Representing the Voronoi diagram
64
32 The divideandconquer approach
67
33 Bisecting chains
73
42 Simplyconnected dcircles
140
43 The Moscow metric
147
Concluding Remarks
159
Bibliography
163
Copyright

Other editions - View all

Common terms and phrases