A simple randomized sieve algorithm for the closest-pair problem

DOI10.1006/inco.1995.1049zbMath0827.68113OpenAlexW2054788982MaRDI 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 problemsieve algorithm

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)

Related Items (18)

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

This page was built for publication: A simple randomized sieve algorithm for the closest-pair problem