Furthest Site Abstract Voronoi Diagrams.

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). [ABSTRACT FROM AUTHOR]