More Web Proxy on the site http://driver.im/

survey

On k-Nearest Neighbor Voronoi Diagrams in the Plane

Author:

Der-Tsai LeeAuthors Info & Claims

IEEE Transactions on Computers, Volume 31, Issue 6

Pages 478 - 487

https://doi.org/10.1109/TC.1982.1676031

Published: 01 June 1982 Publication History

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.

References

[1]

J. L. Bentley, "A survey of techniques for fixed radius near neighbor searching," Dep. Comput. Sci., Univ., Stanford, CA, Rep. STANCS- 75-513, Aug. 1975.

Digital Library

[2]

J. L. Bentley, "Multidimensional binary search trees used for associative searching," Commun. Ass. Comput. Mach., vol. 18, pp. 509-517, Sept. 1975.

Digital Library

[3]

M. Blum, R. Floyd, V. Pratt, R. Rivest, and R. Tarjan, "Time bounds for selection," J. Comput. Syst. Sci., vol. 7, pp. 448-461, Aug 1973.

Digital Library

[4]

W. A. Burkhard and R. M. Keller, "Some approaches to best match file searching," Commun. Ass. Comput. Mach., vol. 16, pp. 230-236, Apr. 1973.

Digital Library

[5]

T. M. Cover and P. E. Hart, "Nearest neighbor pattern classification," IEEE Trans. Inform. Theory, vol. IT-13, pp. 21-27, Jan. 1967.

[6]

D. P. Dobkin and R. J. Lipton, "Multidimensional searching problems," SIAM J. Comput., vol. 5, pp. 181-186, June 1976.

Digital Library

[7]

R. A. Finkle and J. L. Bentley, "Quad trees: A data structure for retrieval on composite keys," Acta Inform., vol. 4, pp. 1-9, 1974.

Digital Library

[8]

J. H. Friedman, F. Baskett, and L. J. Shustek, "An algorithm for finding nearest neighbors," IEEE Trans. Comput., vol. C-24, pp. 1001-1006, Oct. 1975.

Digital Library

[9]

J. H. Friedman, J. L. Bentley, and R. A. Finkel, "An algorithm for finding best matches in logarithmic time," Dep. Comput. Sci., Stanford Univ., Stanford, CA, Rep. STAN-CS-75-482, Feb. 1975.

Digital Library

[10]

K. Fugunaga and P. M. Narendra, "A branch and bound algorithm for computing k-nearest neighbors," IEEE Trans. Comput., vol. C-24, pp. 750-753, July 1975.

Digital Library

[11]

I. G. Gowda, "Dynamic problems in computational geometry," M. Sc. thesis, Univ. of British Columbia, Vancouver, B.C., Canada, 1980.

[12]

D. G. Kirkpatrick, "Optimal search in planar subdivisions," Dep. Comput. Sci., Univ. of British Columbia, Vancouver, B.c., Canada, 1979.

[13]

D. T. Lee, "On finding k nearest neighbors in the plane," M.S. thesis, Rep. R-728, Univ. of Illinois, Urbana, Coordinated Sci. Lab., May 1976.

[14]

D. T. Lee, "Two dimensional Voronoi diagram in the L_p-metric," J. Ass. Comput. Mach., pp. 604-618, Oct. 1980.

Digital Library

[15]

D. T. Lee, "Farthest neighbor Voronoi diagrams and applications," Dep. Elec. Eng. Comput. Sci., Northwestern Univ., Evanston; IL, Tech. Rep. 80-11-FC-04, Nov. 1980.

[16]

D. T. Lee and F. P. Preparata, "Location of a point in a planar subdivision and its applications," SIAM J. Comput., vol. 6, pp. 594-606, Sept. 1977.

Digital Library

[17]

R. J. Lipton and R. E. Tarjan, "Applications of a planar separator theorem," in Proc. i8th iEEE Symp. on Foundations of Comput. Sci., Oct. 1977, pp. 162-170.

Digital Library

[18]

D. O. Loftsgaarden and D. P. Quesenberry, "A non parametric density function," Ann. Math Stat., vol. 36, pp. 1049-1051, 1965.

[19]

F. P. Preparata, "A new approach to planar point location," SIAM J. Comput., vol. 10, pp. 473-482, Aug. 1981.

Digital Library

[20]

C. A. Rogers, Packing and Covering. New York: Cambridge Univ. Press, 1964.

[21]

M. I. Shamos, Computational Geometry. New York: Springer-Verlag,. to be published; and Dep. Comput. Sci., Yale Univ., New Haven, CT, 1977.

[22]

M. I. Shamos and D. Hoey, "Closest-point problems," in Proc. 16th IEEE Symp. on Foundations of Comput. Sci., Oct. 1975, pp. 151- 162.

Digital Library

Cited By

Zhang YVatedka S(2024)Multiple Packing: Lower Bounds via Error ExponentsIEEE Transactions on Information Theory10.1109/TIT.2023.333403270:2(1008-1039)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TIT.2023.3334032
de Berg SStaals F(2023)Dynamic data structures for k-nearest neighbor queriesComputational Geometry: Theory and Applications10.1016/j.comgeo.2022.101976111:COnline publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.comgeo.2022.101976
Sheikhi FZeraatkar BHanaie S(2023)Dot to dot, simple or sophisticated: a survey on shape reconstruction algorithmsActa Informatica10.1007/s00236-023-00443-760:4(335-359)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1007/s00236-023-00443-7
Show More Cited By

On k-Nearest Neighbor Voronoi Diagrams in the Plane
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

K-Nearest Neighbor Finding Using MaxNearestDist

Similarity searching often reduces to finding the k nearest neighbors to a query object. Finding the k nearest neighbors is achieved by applying either a depth- first or a best-first algorithm to the search hierarchy containing the data. These ...
Fast k-Nearest Neighbor Searching in Static Objects

The k-nearest neighbor searching is a classical problem that has been seriously studied, due to its many important applications. The paper proposes an efficient algorithm to search the k-nearest neighbors for static objects. Since locations of static ...
Generalization of Voronoi Diagrams in the Plane

In this paper we study the Voronoi diagram for a set of N line segments and circles in the Euclidean plane. The diagram is a generalization of the Voronoi diagram for a set of points in the plane and has applications in wire layout, facility location, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 31, Issue 6

June 1982

100 pages

ISSN:0018-9340

Issue’s Table of Contents

Copyright © 1982.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 June 1982

Author Tags

Qualifiers

Survey

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

59
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang YVatedka S(2024)Multiple Packing: Lower Bounds via Error ExponentsIEEE Transactions on Information Theory10.1109/TIT.2023.333403270:2(1008-1039)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TIT.2023.3334032
de Berg SStaals F(2023)Dynamic data structures for k-nearest neighbor queriesComputational Geometry: Theory and Applications10.1016/j.comgeo.2022.101976111:COnline publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.comgeo.2022.101976
Sheikhi FZeraatkar BHanaie S(2023)Dot to dot, simple or sophisticated: a survey on shape reconstruction algorithmsActa Informatica10.1007/s00236-023-00443-760:4(335-359)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1007/s00236-023-00443-7
Leroux BRademacher L(2022)Algebraic k-Sets and Generally Neighborly EmbeddingsDiscrete & Computational Geometry10.1007/s00454-021-00340-167:2(605-629)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s00454-021-00340-1
Edelsbrunner HOsang G(2022)A Simple Algorithm for Higher-Order Delaunay Mosaics and Alpha ShapesAlgorithmica10.1007/s00453-022-01027-685:1(277-295)Online publication date: 28-Aug-2022
https://dl.acm.org/doi/10.1007/s00453-022-01027-6
Bläsius TFriedrich TGöbel ALevy JRothenberger RMarx D(2021)The impact of heterogeneity and geometry on the proof complexity of random satisfiabilityProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458068(42-53)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458068
Biswas PDandapat SSairam A(2021)RippleInformation Systems10.1016/j.is.2021.101933105:COnline publication date: 29-Dec-2021
https://dl.acm.org/doi/10.1016/j.is.2021.101933
Edelsbrunner HOsang G(2021)The Multi-Cover Persistence of Euclidean BallsDiscrete & Computational Geometry10.1007/s00454-021-00281-965:4(1296-1313)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s00454-021-00281-9
Chevallier NFruchard ASchmitt DSpehner J(2021)Separation by Convex Pseudo-CirclesDiscrete & Computational Geometry10.1007/s00454-020-00190-365:4(1199-1231)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s00454-020-00190-3
Shenmaier V(2021)Approximation and Complexity of the Capacitated Geometric Median ProblemComputer Science – Theory and Applications10.1007/978-3-030-79416-3_26(422-434)Online publication date: 28-Jun-2021
https://dl.acm.org/doi/10.1007/978-3-030-79416-3_26
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents