Bohler CLiu C.-HPapadopoulou EZavershynskyi M.CHIH-HUNG LIU2022-11-112022-11-11201403029743https://www.scopus.com/inward/record.uri?eid=2-s2.0-84945175456&doi=10.1007%2f978-3-319-13075-0_3&partnerID=40&md5=3c618eff4356b356a457d2187a1c4efdhttps://scholars.lib.ntu.edu.tw/handle/123456789/624649Given 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-andconquer algorithm to compute the order-k abstract Voronoi diagram in expected O(kn1+ε) operations. For solving small sub-instances in the divide-and-conquer process, we also give two sub-algorithms with expected O(k2n log n) and O(n22α(n) log n) time, respectively. This directly implies an O(kn1+ε)-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 Lpnorm, and others. © Springer International Publishing Switzerland 2014.Abstract voronoi diagram; Divide and Conquer; Higher-Order Voronoi Diagram; Randomized algorithmComputational geometry; Concretes; Graphic methods; Combinatorial properties; Divide and conquer; Divide-and-conquer algorithm; Higher-order Voronoi diagrams; Order-k Voronoi diagrams; Randomized Algorithms; Time algorithms; Voronoi diagrams; Algorithmsconference paper10.1007/978-3-319-13075-0_32-s2.0-84945175456