TY - GEN
T1 - Range closest-pair search in higher dimensions
AU - Chan, Timothy M.
AU - Rahul, Saladi
AU - Xue, Jie
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85070578944&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85070578944&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-24766-9_20
DO - 10.1007/978-3-030-24766-9_20
M3 - Conference contribution
AN - SCOPUS:85070578944
SN - 9783030247652
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 269
EP - 282
BT - Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings
A2 - Friggstad, Zachary
A2 - Salavatipour, Mohammad R.
A2 - Sack, Jörg-Rüdiger
PB - Springer
T2 - 16th International Symposium on Algorithms and Data Structures, WADS 2019
Y2 - 5 August 2019 through 7 August 2019
ER -