Liu C.-HPapadopoulou ELee D.T.CHIH-HUNG LIU2022-11-112022-11-11201103029743https://www.scopus.com/inward/record.uri?eid=2-s2.0-80052807378&doi=10.1007%2f978-3-642-23719-5_7&partnerID=40&md5=e915949a6bf0505368a3b7ee238f6b68https://scholars.lib.ntu.edu.tw/handle/123456789/624658This 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.Delaunay graph; Graph-theoretic; K-nearest neighbors; Nearest-neighbors; Output-sensitive; Structural complexity; Time algorithms; Voronoi diagrams; Algorithms; Computational geometry; Graph theory; Graphic methodsconference paper10.1007/978-3-642-23719-5_72-s2.0-80052807378