TY - JOUR
T1 - Range closest-pair search in higher dimensions
AU - Chan, Timothy M.
AU - Rahul, Saladi
AU - Xue, Jie
N1 - Work by the first author has been partially supported by NSF Grant CCF-1814026 . Work by the third author has been partially supported by a Doctoral Dissertation Fellowship from the Graduate School of the University of Minnesota . A preliminary version of this work has appeared in Proceedings of the Algorithms and Data Structures Symposium (WADS), pages 269\u2013282, 2019.
PY - 2020/12
Y1 - 2020/12
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.
KW - Closest pair
KW - Geometric data structures
KW - Range search
UR - http://www.scopus.com/inward/record.url?scp=85086515344&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85086515344&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2020.101669
DO - 10.1016/j.comgeo.2020.101669
M3 - Article
AN - SCOPUS:85086515344
SN - 0925-7721
VL - 91
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
M1 - 101669
ER -