An output-sensitive approach for the L1/L∞ κ-nearest-neighbor voronoi diagram
Journal
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Journal Volume
6942 LNCS
Pages
70-81
Date Issued
2011
Author(s)
Abstract
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.
Other Subjects
Delaunay graph; Graph-theoretic; K-nearest neighbors; Nearest-neighbors; Output-sensitive; Structural complexity; Time algorithms; Voronoi diagrams; Algorithms; Computational geometry; Graph theory; Graphic methods
Type
conference paper