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 language | English (US) |
|---|---|
| Article number | 101669 |
| Journal | Computational Geometry: Theory and Applications |
| Volume | 91 |
| DOIs | |
| State | Published - 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
Chan, T. M., Rahul, S., & Xue, J. (2020). Range closest-pair search in higher dimensions. Computational Geometry: Theory and Applications, 91, [101669]. https://doi.org/10.1016/j.comgeo.2020.101669