文章基本信息

标题：An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams
本地全文：下载
作者：Cecilia Bohler ; Rolf Klein ; Chih-Hung Liu 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：51
页码：21:1-21:15
DOI：10.4230/LIPIcs.SoCG.2016.21
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Order-k Voronoi Diagrams; Abstract Voronoi Diagrams; Randomized Geometric Algorithms