Abstract: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 set 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 size 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.
From: Saeed Odak [view email]
[v1]
Mon, 24 Feb 2025 19:36:12 UTC (115 KB)
[v2]
Sun, 30 Mar 2025 20:20:46 UTC (115 KB)
[v3]
Fri, 26 Jun 2026 20:23:42 UTC (136 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。