AbstractWe 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 perfect hashing to implement the dictionary, the closest pair algorithm runs in O(n) expected time. Alternatively, we can use balanced search trees, and stay within the algebraic computation tree model, which yields an expected running time of O(n log n). In addition to being quick on the average, the algorithm is reliable: we show that the high-probability bound increases only slightly to O(n log n / log log n) if we use hashing and even remains O(n log n) if we use trees as our dictionary implementation. Finally, we give some extensions to the fully dynamic closest pair problem, and to the k closest pair problem.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
Additional Key Words and Phrases: randomized algorithms, closest pair problem
Selected papers that cite this one
- Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen. A reliable randomized algorithm for the closest-pair problem. Journal of Algorithms, 25(1):19-51, October 1997.
- Mordecai Golin, Rajeev Raman, Christian Schwarz, and Michiel Smid. Randomized data structures for the dynamic closest-pair problem. SIAM Journal on Computing, 27(4):1036-1072, August 1998.
- Sanjiv Kapoor and Michiel Smid. New techniques for exact and approximate dynamic closest-point problems. SIAM Journal on Computing, 25(4):775-796, August 1996.
Selected references
- Michael Ben-Or. Lower bounds for algebraic computation trees (preliminary report). In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pages 80-86, Boston, Massachusetts, 25-27 April 1983.
- Jon Louis Bentley and Michael Ian Shamos. Divide-and-conquer in multidimensional space. In Conference Record of the Eighth Annual ACM Symposium on Theory of Computing, pages 220-230, Hershey, Pennsylvania, 3-5 May 1976.
- Hans-Peter Lenhof and Michiel Smid. Enumerating the k closest pairs optimally. In 33rd Annual Symposium on Foundations of Computer Science, pages 380-386, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
- Ketan Mulmuley. Randomized multidimensional search trees: Lazy balancing and dynamic shuffling (extended abstract). In 32nd Annual Symposium on Foundations of Computer Science, pages 180-196, San Juan, Puerto Rico, 1-4 October 1991. IEEE.
- Otfried Schwarzkopf. Dynamic maintenance of geometric structures made easy. In 32nd Annual Symposium on Foundations of Computer Science, pages 197-206, San Juan, Puerto Rico, 1-4 October 1991. IEEE.