Range closest-pair search in higher dimensions

Timothy M. Chan, Saladi Rahul, Jie Xue

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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)
Title of host publicationAlgorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings
EditorsZachary Friggstad, Mohammad R. Salavatipour, Jörg-Rüdiger Sack
Number of pages14
ISBN (Print)9783030247652
StatePublished - 2019
Event16th International Symposium on Algorithms and Data Structures, WADS 2019 - Edmonton, Canada
Duration: Aug 5 2019Aug 7 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11646 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference16th International Symposium on Algorithms and Data Structures, WADS 2019

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this