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 describe an approach to obtaining k-sensitive time bounds. We also point out 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 | 279-286 |
| Number of pages | 8 |
| DOIs | |
| State | Published - 1998 |
| Externally published | Yes |
| Event | Proceedings of the 1998 14th Annual Symposium on Computational Geometry - Minneapolis, MN, USA Duration: Jun 7 1998 → Jun 10 1998 |
Other
| Other | Proceedings of the 1998 14th Annual Symposium on Computational Geometry |
|---|---|
| City | Minneapolis, MN, USA |
| Period | 6/7/98 → 6/10/98 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics