在这篇论文中，我们考虑一个由 $n$ 个点组成的集合 $S$，位于 $\mathbf{R}^d$ 中，$d \text{（维度）} \text{大于等于} 2$ 是常数。设 $H_1,H_2,\text{...},H_{m+1}$ 是一系列按照第一个坐标排序的垂直超平面，使得每两个相邻超平面之间恰好有 $n/m$ 个点。我们定义 $A(S,m)$ 为在所有 $\binom{m+1}{2}$ 个由超平面 $H_i$ 和 $H_j$ 所界定的垂直区域内的不同最近点对的集合。
主要贡献在于，我们构造了一个大小为 $O(n)$ 的数据结构，对于任何垂直查询区域 $Q$，可以在 $O(n^{1/2+\epsilon})$ 时间内报告集合 $Q \cap S$ 中的最近点对。在此之前，没有已知的空间为线性的、查询时间为亚线性的的数据结构。
这项研究为处理高维空间中的最近点对问题提供了新的思路，尤其是在垂直区域的划分与查询中引入了更高效的算法。