2025/02/24 by Biniaz, Ahmad, Bose, Prosenjit, Chung, Chaeyoon +6
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2502.17600
Let S be a set of n points in ℝd, where d ≥ 2 is a constant, and let H1,H2,…,Hm+1 be a sequence of vertical hyperplanes that are sorted by their first coordinates, such that exactly n/m points of S are between any two successive hyperplanes. Let |A(S,m)| be the number of different closest pairs in the m+1 \choose 2 vertical slabs that are bounded by Hi and Hj, over all 1 ≤ i < j ≤ m+1. We prove tight bounds for the largest possible value of |A(S,m)|, over all point sets of size n, and for all values of 1 ≤ m ≤ n. As a result of these bounds, we obtain, for any constant ε>0, a data structure of size O(n), such that for any vertical query slab Q, the closest pair in the set Q ∩ S can be reported in O(n1/2+ε) time. Prior to this work, no linear space data structure with sublinear query time was known.