## Concrete and Abstract Voronoi DiagramsThe 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

### 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 |

163 | |

### Other editions - View all

### Common terms and phrases

abstract Voronoi diagrams admissible curve system admissible neighborhood assertion follows assume augmenting curve bisecting chain bisecting curves bisector borderline boundary bounded C R(p clockwise connected consists contained continuation contour of R(p contradiction convex hull counterclockwise order cross cross-point curve segments cyclical order d-circles d-straight arc defined Definition denote depicted in Figure determined domains dR(p end-if endpoint Euclidean topology Euclidean Voronoi diagram exists faces finitely halfplanes Hence holds induced points infimum interior Lemma line of slope line segment metric space nearest neighbor nice metric non-degenerate non-empty norm O(nlogn p-borderline p-entry point path-connected planar graph plane pointer points induced points of V(S problem Proceedings Proof proximity problems radiating region R(p scan Section shown in Figure simple closed curve simply-connected sites(u subsets system of bisecting Theorem triangle inequality unbounded V(L U vertex vertices Voronoi regions