MPI-I-92-135
Furthest site abstract Voronoi diagrams
Mehlhorn, Kurt and Meiser, Stefan and Rasch, Ronald
April 1992, 25 pages.
.
Status: available - back from printing
Abstract Voronoi diagrams were introduced by R. Klein as a
unifying approach to Voronoi diagrams. In this paper we study
furthest site abstract Voronoi diagrams and give a unified mathematical
and algorithmic treatment for them. In particular, we show that furthest
site abstract Voronoi diagrams are trees, have
linear size, and that, given a set of $n$ sites, the
furthest site abstract Voronoi diagram can be computed by a
randomized algorithm in expected time $O(n\log n)$.
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1992-135
BibTeX
@TECHREPORT{MehlhornMeiserRasch,
AUTHOR = {Mehlhorn, Kurt and Meiser, Stefan and Rasch, Ronald},
TITLE = {Furthest site abstract Voronoi diagrams}},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-92-135},
MONTH = {April},
YEAR = {1992},
ISSN = {0946-011X},
}