hide
Free keywords:
-
Abstract:
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)$.
