2026-07-25T12:25:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5913 2024-03-06T10:37:16Z ddc:004 open_access

An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams Bohler, Cecilia Klein, Rolf Liu, Chih-Hung Order-k Voronoi Diagrams Abstract Voronoi Diagrams Randomized Geometric Algorithms 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. Due to those axioms, 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, this kind of run time with a polylog factor to the number of faces was only achieved for point sites in the L_1 or Euclidean metric before. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Cecilia Bohler and Rolf Klein and Chih-Hung Liu 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.21 urn:nbn:de:0030-drops-59135 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.21 eng https://creativecommons.org/licenses/by/3.0/legalcode