A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams

Given a set of sites in the plane, their order-k Voronoi diagram partitions the plane into regions such that all points within one region have the same k nearest sites. The order-k abstract Voronoi diagram is defined in terms of bisecting curves satisfying some simple combinatorial properties, rather than the geometric notions of sites and distance, and it represents a wide class of order-k concrete Voronoi diagrams. In this paper we develop a randomized divide-and-conquer algorithm to compute the order-k abstract Voronoi diagram in expected O(kn(1+epsilon)) operations. For solving small sub-instances in the divide-and-conquer process, we also give two sub-algorithms with expected O(k(2)n log n) and O(n 2 2 a(n) log n) time, respectively. This directly implies an O(kn(1+epsilon))-time algorithm for several concrete order-k instances such as points in any convex distance, disjoint line segments and convex polygons of constant size in the L-p norm, and others.