On k-Nearest Neighbor Voronoi Diagrams in the Plane
- 1 June 1982
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-31 (6) , 478-487
- https://doi.org/10.1109/tc.1982.1676031
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
This publication has 13 references indexed in Scilit:
- A New Approach to Planar Point LocationSIAM Journal on Computing, 1981
- Two-Dimensional Voronoi Diagrams in theLp-MetricJournal of the ACM, 1980
- Location of a Point in a Planar Subdivision and Its ApplicationsSIAM Journal on Computing, 1977
- Applications of a planar separator theoremPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1977
- Multidimensional Searching ProblemsSIAM Journal on Computing, 1976
- An Algorithm for Finding Nearest NeighborsIEEE Transactions on Computers, 1975
- A Branch and Bound Algorithm for Computing k-Nearest NeighborsIEEE Transactions on Computers, 1975
- Time bounds for selectionJournal of Computer and System Sciences, 1973
- Nearest neighbor pattern classificationIEEE Transactions on Information Theory, 1967
- A Nonparametric Estimate of a Multivariate Density FunctionThe Annals of Mathematical Statistics, 1965