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.

Bibliographic Information

Book Title: Concrete and Abstract Voronoi Diagrams
Authors: Rolf Klein
Series Title: Lecture Notes in Computer Science
DOI: https://doi.org/10.1007/3-540-52055-4
Publisher: Springer Berlin, Heidelberg
eBook Packages: Springer Book Archive
Copyright Information: Springer-Verlag Berlin Heidelberg 1989
Softcover ISBN: 978-3-540-52055-9Published: 20 December 1989
eBook ISBN: 978-3-540-46874-5Published: 30 June 2005
Series ISSN: 0302-9743
Series E-ISSN: 1611-3349
Edition Number: 1
Number of Pages: IV, 169
Topics: Theory of Computation, Computer Applications, Information Storage and Retrieval, Data Structures, Algorithm Analysis and Problem Complexity, Computer Graphics

Publish with us

Policies and ethics

Concrete and Abstract Voronoi Diagrams

Overview

Access this book

Other ways to access

Table of contents (6 chapters)

Front Matter

Introduction

Voronoi diagrams in nice metrics

Abstract Voronoi diagrams

Computing abstract Voronoi diagrams

Acyclic partitions

Concluding remarks

Back Matter

Keywords

About this book

Bibliographic Information

Publish with us

Search

Navigation