On the construction of abstract Voronoi diagrams

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