Range closest-pair search in higher dimensions

Timothy M. Chan, Saladi Rahul, Jie Xue

Research output: Contribution to journalArticle

Abstract

Range closest-pair (RCP) search is a range-search variant of the classical closest-pair problem, which aims to store a given set S of points into some space-efficient data structure such that when a query range Q is specified, the closest pair in S∩Q can be reported quickly. RCP search has received attention over years, but the primary focus was only on R2. In this paper, we study RCP search in higher dimensions. We give the first nontrivial RCP data structures for orthogonal, simplex, halfspace, and ball queries in Rd for any constant d. Furthermore, we prove a conditional lower bound for orthogonal RCP search for d≥3.

Original languageEnglish (US)
Article number101669
JournalComputational Geometry: Theory and Applications
Volume91
DOIs
StatePublished - Dec 2020

Keywords

  • Closest pair
  • Geometric data structures
  • Range search

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Range closest-pair search in higher dimensions'. Together they form a unique fingerprint.

  • Cite this