https://scholars.lib.ntu.edu.tw/handle/123456789/624636
Title: | An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams | Authors: | Bohler C Klein R CHIH-HUNG LIU |
Keywords: | Abstract Voronoi diagrams; Computational geometry; Order-k Voronoi diagrams; Randomized geometric algorithms | Issue Date: | 2019 | Journal Volume: | 81 | Journal Issue: | 6 | Start page/Pages: | 2317-2345 | Source: | Algorithmica | Abstract: | 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 2n+ nlog 3n) steps, where O(k(n- k)) is the number of faces in the worst case. This result applies to disjoint line segments in the Lp 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 L1 or Euclidean metric before. © 2018, Springer Science+Business Media, LLC, part of Springer Nature. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85064920923&doi=10.1007%2fs00453-018-00536-7&partnerID=40&md5=9f1549531df3d9cd82194da59ff12790 https://scholars.lib.ntu.edu.tw/handle/123456789/624636 |
ISSN: | 01784617 | DOI: | 10.1007/s00453-018-00536-7 | SDG/Keyword: | Computational geometry; Nearest neighbor search; Euclidean metrics; Geometric algorithm; K-nearest neighbors; Order-k Voronoi diagrams; Planar subdivision; Randomized Algorithms; Randomized incremental construction; Voronoi diagrams; Graphic methods |
Appears in Collections: | 電機工程學系 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.