Abstract
We give an algorithm that computes the closest pair in a set ofn points ink-dimensional space on-line, inO(n logn) time. The algorithm only uses algebraic functions and, therefore, is optimal. The algorithm maintains a hierarchical subdivision ofk-space into hyperrectangles, which is stored in a binary tree. Centroids are used to maintain a balanced decomposition of this tree.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. L. Bentley and M. I. Shamos. Divide-and-conquer in multidimensional space.Proc. 8th Annual ACM Symp. on Theory of Computing, 1976, pp. 220–230.
B. Chazelle. A theorem on polygon cutting with applications.Proc. 23rd Annual IEEE Symp. on Foundations of Computer Science, 1982, pp. 339–349.
M. T. Dickerson and R. S. Drysdale. Enumeratingk distances forn points in the plane.Proc. 7th ACM Symp. on Computational Geometry, 1991, pp. 234–238.
L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. E. Tarjan. Linear time algorithms for visibility and shortest path problems inside triangulated simple polygons.Algorithmica 2 (1987), 209–233.
J. Hershberger. Efficient Algorithms for Shortest Path and Visibility Problems. Report No. STAN-CS-87-1163, Stanford University, Stanford, CA, 1987.
M. H. Overmars.The Design of Dynamic Data Structures. Lecture Notes in Computer Science, Vol. 156. Springer-Verlag, Berlin, 1983.
F. P. Preparata and M. I. Shamos.Computational Geometry, An Introduction. Springer-Verlag, New York, 1985.
J. S. Salowe. Enumerating interdistances in space.Internat. J. Comput. Geom. Appl. 2 (1992), 49–59.
C. Schwarz and M. Smid. AnO(n logn log logn) algorithm for the on-line closest pair problem.Proc. 3rd Annual ACM-SIAM Symp. on Discrete Algorithms, 1992, pp. 280–285.
M. I. Shamos and D. Hoey. Closest-point problems.Proc. 16th Annual IEEE Symp. on Foundations of Computer Science, 1975, pp. 151–162.
M. Smid. Maintaining the minimal distance of a point set in less than linear time.Algorithms Rev. 2 (1991), 33–44.
M. Smid. Rectangular point location and the dynamic closest pair problem. Proc. 2nd Annual Internat. Symp. on Algorithms. Lecture Notes in Computer Science, Vol. 557. Springer-Verlag, Berlin, 1991, pp. 364–374.
M. Smid. Maintaining the minimal distance of a point set in polylogarithmic time.Discrete Comput. Geom. 7 (1992), 415–431.
K. J. Supowit. New techniques for some dynamic closest-point and farthest-point problems.Proc. 1st Annual ACM-SIAM Symp. on Discrete Algorithms, 1990, pp. 84–90.
P. M. Vaidya. AnO(n logn) algorithm for the all-nearest-neighbors problem.Discrete Comput. Geom. 4 (1989), 101–115.
Author information
Authors and Affiliations
Additional information
Communicated by Kurt Mehlhorn.
These authors were supported by the ESPRIT II Basic Research Actions Program, under Contract No. 3075 (project ALCOM).
This author was supported in part by the National Science and Engineering Research Council of Canada.
Rights and permissions
About this article
Cite this article
Schwarz, C., Smid, M. & Snoeyink, J. An optimal algorithm for the on-line closest-pair problem. Algorithmica 12, 18–29 (1994). https://doi.org/10.1007/BF01377181
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01377181