https://scholars.lib.ntu.edu.tw/handle/123456789/624647
標題: | The k-Nearest-Neighbor Voronoi Diagram Revisited | 作者: | Liu C.-H Papadopoulou E Lee D.-T. CHIH-HUNG LIU |
關鍵字: | Higher-order Voronoi diagrams; k Neareast neighbors; Segment dragging queries; Voronoi diagrams | 公開日期: | 2015 | 卷: | 71 | 期: | 2 | 起(迄)頁: | 429-449 | 來源出版物: | Algorithmica | 摘要: | We revisit the k-nearest-neighbor (k-NN) Voronoi diagram and present a new paradigm for its construction. We introduce the k-NN Delaunay graph, which is the graph-theoretic dual of the k-NN Voronoi diagram, and use it as a base to directly compute this diagram in R2. We implemented our paradigm in the L1 and L∞ metrics, using segment-dragging queries, resulting in the first output-sensitive, O((n+m)logn)-time algorithm to compute the k-NN Voronoi diagram of n points in the plane, where m is the structural complexity (size) of this diagram. We also show that the structural complexity of the k-NN Voronoi diagram in the L∞ (equiv. L1) metric is O(min{k(n−k),(n−k)2}). Efficient implementation of our paradigm in the L2 (resp. Lp, 1<p<∞) metric remains an open problem. © 2013, Springer Science+Business Media New York. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-84926277048&doi=10.1007%2fs00453-013-9809-9&partnerID=40&md5=46773f486feca2a29ef2bd6e8de87d40 https://scholars.lib.ntu.edu.tw/handle/123456789/624647 |
ISSN: | 01784617 | DOI: | 10.1007/s00453-013-9809-9 | SDG/關鍵字: | Graph theory; Graphic methods; Motion compensation; Nearest neighbor search; Efficient implementation; Higher-order Voronoi diagrams; K-nearest neighbors; Output-sensitive; Segment dragging queries; Structural complexity; Time algorithms; Voronoi diagrams; Computational geometry |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。