On the construction of abstract Voronoi diagrams

Abstract

We show that the abstract Voronoi diagram of n sites in the plane can be constructed in time O(n log n) by a randomized algorithm. This yields an alternative, but simpler, O(n log n) algorithm in many previously considered cases and the first O(n log n) algorithm in some cases, e.g., disjoint convex sites with the Euclidean distance function. Abstract Voronoi diagrams are given by a family of bisecting curves and were recently introduced by Klein [Kl88a]. Our algorithm is based on Clarkson and Shor's randomized incremental construction technique [CS].