Article

Free access

An optimal algorithm for the on-line closest-pair problem

Authors:

Christian Schwarz,

Michiel Smid,

Jack SnoeyinkAuthors Info & Claims

SCG '92: Proceedings of the eighth annual symposium on Computational geometry

Pages 330 - 336

https://doi.org/10.1145/142675.142742

Published: 01 July 1992 Publication History

PDF eReader

Abstract

We give an algorithm that computes the closest pair in a set of n points in k-dimensional space on-line, in O(n log n) time. The algorithm only uses algebraic functions and, therefore, is optimal. The algorithm maintains a hierarchical subdivision of k-sapce into hyper-rectangles, which is stored in a binary tree. Centroids are used to maintain a balanced decomposition of this tree.

References

[1]

J.L. Bentley and M.I. Shamos. Divide-and-conquer in multidimensional space. Proc. 8th Annual ACM Syrup. on Theory of Computing, 1970, pp. 220-230.

Digital Library

Google Scholar

[2]

B. Chazelle. A theorem on polygon cutting with applications. Proc. 23rd Annum IEEE Symp. on Foundations of Computer Science, 1982, pp. 339- 349.

Digital Library

Google Scholar

[3]

M.T. Dickerson and R.S. Drysdale. Enumerating k distances for n points in the plane. Proc. 7th ACM Symp. on Computational Geometry, 1991, pp. 234- 238.

Digital Library

Google Scholar

[4]

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), pp. 209-233.

Digital Library

Google Scholar

[5]

M.H. Overmars. The Design of Dynamic Data Structures. Lecture Notes in Computer Science, Vol. 156, Springer-Verlag, Berlin, 1983.

Digital Library

Google Scholar

[6]

F.P. Preparata and M.I. Shamos. Computational Geometry, an Introduction. Springer-Verlag, New York, 1985.

Digital Library

Google Scholar

[7]

J.S. Salowe. Shallow interdistance selection and interdistance enumeration. Proc. WADS'91, LNCS Vol. 519, Springer-Verlag, Berlin, 1991, pp. 117- 128.

Crossref

Google Scholar

[8]

C. Schwarz and M. Staid. An O(nlognloglogn) algorithm for the on-line closest pair problem. To appear in: Proceedings 3rd Annum ACM-SIAM Symp. on Discrete Algorithms, 1992.

Digital Library

Google Scholar

[9]

M.I. Shamos and D. Hoey. Closest-pair problems. Proc. 16th Annual IEEE Symp. on Foundations of Computer Science, 1975, pp. 151-162.

Google Scholar

[10]

M. Staid. Maintaining the minimal distance of a point set in less than linear time. Algorithms Review 2 (1991), pp. 33-44.

Google Scholar

[11]

M. Smid. Dynamic rectangular point location, with an application to the closest pair problem. Report MPI-I-91-101, Max-Planck-Institut fiir Informatik, Saarbriicken, 1991. See also: Proc. 2nd Annual international Symp. on Algorithms, 1991.

Digital Library

Google Scholar

[12]

M. Smid. Maintaining the minimal distance of a point set in polylogariihmic time (revised version). Report MPI-I-91-103, Max-Planck-Institut fiir Informatik, Saarbriicken, 1991. See also: Proc. 2nd Annual ACM-SIAM Symp. on Discrete Algorithms, 1991, pp. 1-6.

Digital Library

Google Scholar

[13]

K.J. Supowit. New techniques for some dynamic closest-point and farthesi-point problems. Proc. 1st Annual ACM-SIAM Symp. on Discrete Algorithms, 1990, pp. 84-90.

Digital Library

Google Scholar

[14]

P.M. Vaiaya. An O(nlogn) algorithm for the all-nearest-neighbors problem. Discrete Comput. Geom. 4 (1989), pp. 101-115.

Digital Library

Google Scholar

Cited By

View all

Zhou YYu H(2015)An Efficient Comparison-Based Deterministic Algorithm to Solve the Closest Pair Problem2015 8th International Conference on Intelligent Computation Technology and Automation (ICICTA)10.1109/ICICTA.2015.45(145-148)Online publication date: Jun-2015
https://doi.org/10.1109/ICICTA.2015.45
Angiulli FPizzuti C(2005)Approximate k-Closest-Pairs in Large High-Dimensional Data SetsJournal of Mathematical Modelling and Algorithms10.1007/s10852-004-4080-34:2(149-179)Online publication date: Jun-2005
https://doi.org/10.1007/s10852-004-4080-3
Cohen RTamassia R(2005)Combine and conquer: A general technique for dynamic algorithmsAlgorithms—ESA '9310.1007/3-540-57273-2_47(97-108)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-57273-2_47
Show More Cited By

Index Terms

An optimal algorithm for the on-line closest-pair problem

Recommendations

A Reliable Randomized Algorithm for the Closest-Pair Problem

The following two computational problems are studied:Duplicate grouping:Assume thatnitems are given, each of which is labeled by an integer key from the set {0, ,U 1}. Store the items in an array of sizensuch that items with the same key occupy a ...
An O(n log n log log n) Algorithm for the On-line Closest Pair Problem
SODA '92: Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms

Let V be a set of n points in k-dimensional space. It is shown how the closest pair in V can be maintained under insertions in O(log n log log n) amortized time, using O(n) amortized time, using O(n) space. Distances are measured in the L_t-metric, where ...
Simple randomized algorithms for closest pair problems

We present a conceptually simple, randomized incremental algorithm for finding the closest pair in a set of n points in D-dimensional space, where D ≥ 2 is a fixed constant. Much of the work reduces to maintaining a dynamic dictionary. Using dynamic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCG '92: Proceedings of the eighth annual symposium on Computational geometry

July 1992

384 pages

ISBN:0897915178

DOI:10.1145/142675

Chairman:
David Avis

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1992

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SOCG92

Sponsor:

SOCG92: 8th Annual Symposium on Computational Geometry 1992

June 10 - 12, 1992

Berlin, Germany

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
484
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)10

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhou YYu H(2015)An Efficient Comparison-Based Deterministic Algorithm to Solve the Closest Pair Problem2015 8th International Conference on Intelligent Computation Technology and Automation (ICICTA)10.1109/ICICTA.2015.45(145-148)Online publication date: Jun-2015
https://doi.org/10.1109/ICICTA.2015.45
Angiulli FPizzuti C(2005)Approximate k-Closest-Pairs in Large High-Dimensional Data SetsJournal of Mathematical Modelling and Algorithms10.1007/s10852-004-4080-34:2(149-179)Online publication date: Jun-2005
https://doi.org/10.1007/s10852-004-4080-3
Cohen RTamassia R(2005)Combine and conquer: A general technique for dynamic algorithmsAlgorithms—ESA '9310.1007/3-540-57273-2_47(97-108)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-57273-2_47
Datta ALenhof HSchwarz CSmid M(2005)Static and dynamic algorithms for k-point clustering problemsAlgorithms and Data Structures10.1007/3-540-57155-8_254(265-276)Online publication date: 9-Jun-2005
https://doi.org/10.1007/3-540-57155-8_254
Golin M(2005)Dynamic closest pairs — A probabilistic approachAlgorithm Theory — SWAT '9210.1007/3-540-55706-7_31(340-351)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-55706-7_31
Eppstein DKarloff H(1998)Fast hierarchical clustering and other applications of dynamic closest pairsProceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms10.5555/314613.315030(619-628)Online publication date: 1-Jan-1998
https://dl.acm.org/doi/10.5555/314613.315030
Dietzfelbinger MHagerup TKatajainen JPenttonen M(1997)A Reliable Randomized Algorithm for the Closest-Pair ProblemJournal of Algorithms10.1006/jagm.1997.087325:1(19-51)Online publication date: 1-Oct-1997
https://dl.acm.org/doi/10.1006/jagm.1997.0873
Callahan PKosaraju SClarkson K(1995)Algorithms for dynamic closest pair and n-body potential fieldsProceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/313651.313705(263-272)Online publication date: 22-Jan-1995
https://dl.acm.org/doi/10.5555/313651.313705
Bespamyatnikh SSnoeyink J(1995)An optimal algorithm for closest pair maintenance (extended abstract)Proceedings of the eleventh annual symposium on Computational geometry10.1145/220279.220296(152-161)Online publication date: 1-Sep-1995
https://dl.acm.org/doi/10.1145/220279.220296
Eppstein D(1995)Dynamic Euclidean minimum spanning trees and extrema of binary functionsDiscrete & Computational Geometry10.1007/BF0257403013:1(111-122)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.1007/BF02574030
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A Reliable Randomized Algorithm for the Closest-Pair Problem

An O(n log n log log n) Algorithm for the On-line Closest Pair Problem

Simple randomized algorithms for closest pair problems