An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams.

Given a set of n sites in the plane, the order-k Voronoi diagram is a planar subdivision such that all points in a region share the same k nearest sites. The order-k Voronoi diagram arises for the k-nearest-neighbor problem, and there has been a lot of work for point sites in the Euclidean metric. In this paper, we study order-k Voronoi diagrams defined by an abstract bisecting curve system that satisfies several practical axioms, and thus our study covers many concrete order-k Voronoi diagrams. We propose a randomized incremental construction algorithm that runs in O (k (n - k) log 2 n + n log 3 n) steps, where O (k (n - k)) is the number of faces in the worst case. This result applies to disjoint line segments in the L p norm, convex polygons of constant size, points in the Karlsruhe metric, and so on. In fact, a running time with a polylog factor to the number of faces was only achieved for point sites in the L 1 or Euclidean metric before. [ABSTRACT FROM AUTHOR]