Title :
On k-Nearest Neighbor Voronoi Diagrams in the Plane
Author_Institution :
Department of Electrical Engineering and Computer Science, Northwestern University
fDate :
6/1/1982 12:00:00 AM
Abstract :
The notion of Voronoi diagram for a set of N points in the Euclidean plane is generalized to the Voronoi diagram of order k and an iterative algorithm to construct the generalized diagram in 0(k2N log N) time using 0(k2(N − k)) space is presented. It is shown that the k-nearest neighbor problem and other seemingly unrelated problems can be solved efficiently with the diagram.
Keywords :
Analysis of algorithm; Voronoi diagram; computational complexity; divide and conquer technique; k-nearest neighbors; point location; Computational complexity; Costs; Data structures; Helium; Information retrieval; Iterative algorithms; Nearest neighbor searches; Pattern classification; Testing; Time measurement; Analysis of algorithm; Voronoi diagram; computational complexity; divide and conquer technique; k-nearest neighbors; point location;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1982.1676031
