https://scholars.lib.ntu.edu.tw/handle/123456789/624645
標題: | An efficient randomized algorithm for higher-order abstract Voronoi diagrams | 作者: | Bohler C Klein R CHIH-HUNG LIU |
關鍵字: | Abstract Voronoi diagrams; Order-k Voronoi diagrams; Randomized geometric algorithms | 公開日期: | 2016 | 卷: | 51 | 起(迄)頁: | 21.1-21.15 | 來源出版物: | Leibniz International Proceedings in Informatics, LIPIcs | 摘要: | 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) log2 n + n log3 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 Lp 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 L1 or Euclidean metric before. © Cecilia Bohler, Rolf Klein, and Chih-Hung Liu. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-84976878553&doi=10.4230%2fLIPIcs.SoCG.2016.21&partnerID=40&md5=c02b7e6f6647e5d10bbe461bc127b777 https://scholars.lib.ntu.edu.tw/handle/123456789/624645 |
ISSN: | 18688969 | DOI: | 10.4230/LIPIcs.SoCG.2016.21 | SDG/關鍵字: | Algorithms; Computational geometry; 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 |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。