FURTHEST SITE ABSTRACT VORONOI DIAGRAMS
- 1 December 2001
- journal article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 11 (6) , 583-616
- https://doi.org/10.1142/s0218195901000663
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).Keywords
This publication has 4 references indexed in Scilit:
- Applications of random sampling to on-line algorithms in computational geometryDiscrete & Computational Geometry, 1992
- Applications of random sampling in computational geometry, IIDiscrete & Computational Geometry, 1989
- Voronoi diagrams and arrangementsDiscrete & Computational Geometry, 1986
- Voronoi diagrams from convex hullsInformation Processing Letters, 1979