On enumerating and selecting distances

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)291-304
Number of pages14
JournalInternational Journal of Computational Geometry and Applications
Volume11
Issue number3
DOIs
StatePublished - Jun 1 2001
Externally publishedYes

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

Fingerprint Dive into the research topics of 'On enumerating and selecting distances'. Together they form a unique fingerprint.

Cite this