AbstractWe present a simple randomized algorithm for finding the Closest Foreign Pair, in a set of n points in D-dimensional space, where D >= 2 is a fixed constant and the distances are measured in the L1 and the Linfty metric. The algorithm runs in O(n logD-1 n/log log n) time with high probability for the Linfty metric and in O(n log2D-1 - 1n / log log n) time with high probability for the L1 metric.
Categories and Subject Descriptors: I.1.2 [Algebraic Manipulation]: Algorithms; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling
Additional Key Words and Phrases: closest foreign pair, computational geometry, randomized algorithms
Selected references
- Michael L. Fredman and Dan E. Willard. BLASTING through the information theoretic barrier with FUSION TREES. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 1-7, Baltimore, Maryland, 14-16 May 1990.
- Michael L. Fredman and Dan E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. In 31st Annual Symposium on Foundations of Computer Science, volume II, pages 719-725, St. Louis, Missouri, 22-24 October 1990. IEEE.