Range closest-pair search in higher dimensions

Timothy M. Chan, Saladi Rahul, Jie Xue

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

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)
Title of host publicationAlgorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings
EditorsZachary Friggstad, Mohammad R. Salavatipour, Jörg-Rüdiger Sack
PublisherSpringer-Verlag
Pages269-282
Number of pages14
ISBN (Print)9783030247652
DOIs
StatePublished - Jan 1 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

Conference

Conference16th International Symposium on Algorithms and Data Structures, WADS 2019
CountryCanada
CityEdmonton
Period8/5/198/7/19

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Chan, T. M., Rahul, S., & Xue, J. (2019). Range closest-pair search in higher dimensions. In Z. Friggstad, M. R. Salavatipour, & J-R. Sack (Eds.), Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings (pp. 269-282). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11646 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-030-24766-9_20