https://scholars.lib.ntu.edu.tw/handle/123456789/624658
標題: | An output-sensitive approach for the L1/L∞ κ-nearest-neighbor voronoi diagram | 作者: | Liu C.-H Papadopoulou E Lee D.T. CHIH-HUNG LIU |
公開日期: | 2011 | 卷: | 6942 LNCS | 起(迄)頁: | 70-81 | 來源出版物: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | 摘要: | This paper revisits the k-nearest-neighbor (κ-NN) Voronoi diagram and presents the first output-sensitive paradigm for its construction. It introduces the k-NN Delaunay graph, which corresponds to the graph theoretic dual of the κ-NN Voronoi diagram, and uses it as a base to directly compute the κ-NN Voronoi diagram in R 2. In the L1, L∞ metrics this results in O((n+m)log n) time algorithm, using segment-dragging queries, where m is the structural complexity (size) of the κ-NN Voronoi diagram of n point sites in the plane. The paper also gives a tighter bound on the structural complexity of the κ-NN Voronoi diagram in the L∞ (equiv. L 1) metric, which is shown to be O(min{∈(n-κ), (n-κ)2}). © 2011 Springer-Verlag Berlin Heidelberg. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-80052807378&doi=10.1007%2f978-3-642-23719-5_7&partnerID=40&md5=e915949a6bf0505368a3b7ee238f6b68 https://scholars.lib.ntu.edu.tw/handle/123456789/624658 |
ISSN: | 03029743 | DOI: | 10.1007/978-3-642-23719-5_7 | SDG/關鍵字: | Delaunay graph; Graph-theoretic; K-nearest neighbors; Nearest-neighbors; Output-sensitive; Structural complexity; Time algorithms; Voronoi diagrams; Algorithms; Computational geometry; Graph theory; Graphic methods |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。