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. Abstract Voronoi diagrams are given by a family of bisecting curves and were recently introduced by Klein. Our algorithm is based on Clarkson and Shor's randomised incrememntal construction technique.