Enumerating the k closest pairs optimally
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 380-386
- https://doi.org/10.1109/sfcs.1992.267752
Abstract
Let S be a set of n points in D-dimensional space, where D is a constant, and let k be an integer between 1 and (/sub 2//sup n/) An algorithm is given that computes the k closest pairs in the set S in O(nlogn+k) time, using O(n+k) space. The algorithm fits in the algebraic decision tree model and is, therefore, optimal.Keywords
This publication has 10 references indexed in Scilit:
- Shallow interdistance selection and interdistance enumerationPublished by Springer Nature ,2005
- ENUMERATING INTERDISTANCES IN SPACEInternational Journal of Computational Geometry & Applications, 1992
- An optimal algorithm for the on-line closest-pair problemPublished by Association for Computing Machinery (ACM) ,1992
- Finding k farthest pairs and k closest/farthest bichromatic pairs for points in the planePublished by Association for Computing Machinery (ACM) ,1992
- Enumerating k distances for n points in the planePublished by Association for Computing Machinery (ACM) ,1991
- Selecting distances in the planePublished by Association for Computing Machinery (ACM) ,1990
- L-infinity interdistance selection by parametric searchInformation Processing Letters, 1989
- Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $SIAM Journal on Computing, 1978
- Divide-and-conquer in multidimensional spacePublished by Association for Computing Machinery (ACM) ,1976
- Closest-point problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1975