Abstract
Given an n-point set, the problems of enumerating the k closest pairs and selecting the k-th smallest distance are revisited. For the enumeration problem, we give simpler randomized and deterministic algorithms with O(n log n + k) running time in any fixed-dimensional Euclidean space. For the selection problem, we give a randomized algorithm with running time O(n log n+n2/3k1/3 log5/3 n) in the Euclidean plane. We also describe output-sensitive results for halfspace range counting that are of use in more general distance selection problems. None of our algorithms requires parametric search.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 291-304 |
| Number of pages | 14 |
| Journal | International Journal of Computational Geometry and Applications |
| Volume | 11 |
| Issue number | 3 |
| DOIs | |
| State | Published - Jun 2001 |
| Externally published | Yes |
Keywords
- Closest pairs
- Distance enumeration
- Distance selection
- Randomized algorithms
- Range counting
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Theory and Mathematics
- Computational Mathematics
- Applied Mathematics