A simple randomized sieve algorithm for the closest-pair problem

DOI10.1006/inco.1995.1049zbMath0827.68113MaRDI QIDQ1891130

Samir Khuller, Yossi Matias

Publication date: 28 May 1995

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1995.1049

zbMATH Keywords

closest-pair problem; sieve algorithm

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68W10: Parallel algorithms in computer science

Related Items

ON ENUMERATING AND SELECTING DISTANCES, Unnamed Item, Unnamed Item, Unnamed Item, On the Complexity of Closest Pair via Polar-Pair of Point-Sets, Improved Approximate Rips Filtrations with Shifted Integer Lattices, A unified approach to tail estimates for randomized incremental construction, On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic, Efficient randomized incremental algorithm for the closest pair problem using Leafary trees, Efficiently approximating color-spanning balls, All-maximum and all-minimum problems under some measures, Approximate \(k\)-closest-pairs in large high-dimensional data sets, Polynomial-sized topological approximations using the permutahedron, On closest pair in Euclidean metric: monochromatic is as hard as bichromatic, Improved approximate Rips filtrations with shifted integer lattices and cubical complexes, A new coding-based algorithm for finding closest pair of vectors, On the Complexity of Closest Pair via Polar-Pair of Point-Sets, TIGHT QUANTUM BOUNDS FOR COMPUTATIONAL GEOMETRY PROBLEMS