A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams

摘要: Given a set of n sites in the plane, their order-k Voronoi diagram partitions plane into regions such that all points within one region have same k nearest sites. The abstract offers unifying framework represents wide range concrete diagrams. It is defined terms bisecting curves satisfying some simple combinatorial properties, rather than geometric notions and distance.In this paper we develop randomized divide-and-conquer algorithm to compute expected O ( 1 + e ) operations. For solving small sub-instances process, also give two auxiliary algorithms with 2 log ź α time, respectively, where inverse Ackermann function. Our approach directly implies an -time for several instances as any convex distance, disjoint line segments or polygons constant size L p norms, others. provides basic techniques can enable application well-known random sampling construction diagrams setting non-point