2019/05/03 by Timothy M. Chan, Chan, Timothy M., Saladi Rahul +3
Computer Science · Engineering · #Advanced Image and Video Retrieval Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Robotics and Sensor-Based Localization #cs.CG
paper · pdf · doi:10.48550/arxiv.1905.01029
arxiv created 2019/05/03 · openalex publication_date 2019/05/03 · arxiv updated 2019/05/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ℝ2. 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 ℝd for any constant d. Furthermore, we prove a conditional lower bound for orthogonal RCP search for d ≥ 3.