The average performance analysis of a closest?pair algorithm
- 1 January 1984
- journal article
- research article
- Published by Taylor & Francis in International Journal of Computer Mathematics
- Vol. 16 (2) , 125-130
- https://doi.org/10.1080/00207168408803430
Abstract
Bentley proposed a divide‐and‐conquer approach to solve the planar closest pair problem. In this paper, we shall show that the average case performance of this algorithm is proportional to the number of poins being examined.Keywords
This publication has 9 references indexed in Scilit:
- The extendible cell method for closest point problemsBIT Numerical Mathematics, 1982
- Multidimensional divide-and-conquerCommunications of the ACM, 1980
- A note on Rabin's nearest-neighbor algorithmInformation Processing Letters, 1979
- Divide and conquer for linear expected timeInformation Processing Letters, 1978
- Finding nearest neighboursInformation Processing Letters, 1976
- Finding near neighbours in K-dimensional spaceInformation Processing Letters, 1975
- On the homogeneous planar Poisson point processMathematical Biosciences, 1970
- Stochastic Point Processes: Limit TheoremsThe Annals of Mathematical Statistics, 1967
- A Lower Bound for the Expected Travel Among $m$ Random PointsThe Annals of Mathematical Statistics, 1948