Tight Bounds on the Number of Closest Pairs in Vertical Slabs

Let $S$ be a set of $n$ points in $\mathbb{R}^d$, where $d \geq 2$ is a constant, and let $H_1,H_2,\ldots,H_{m+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 $H_i$ and $H_j$, over all $1 \leq i < j \leq 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 \leq m \leq n$. As a result of these bounds, we obtain, for any constant $\epsilon>0$, a data structure of size $O(n)$, such that for any vertical query slab $Q$, the closest pair in the set $Q \cap S$ can be reported in $O(n^{1/2+\epsilon})$ time. Prior to this work, no linear space data structure with sublinear query time was known.