在二维笛卡儿平面上存在一个点集P，我们可能需要进行这样的查询“在P中离x点最近的点是哪个？”。x可能并不属于P。这些查询也可以扩展到n维的空间。初级的实现方式是探测所有P中的点，是一种线性的算法。由于我们一开始就能知道P，所以应该能够对P的信息构建合理的数据结构，在查询时抛弃一些不必要的点，加快查询的速度。
也许我们可以将平面分成k2个格子，每个格子的大小是固定的，m×m，如图9-18a。在P中有10个点被放入了9个相邻的格子中。当寻找x的最邻近点时，在它周围的格子中寻找。如果格子是非空的，那么我们只需要在这些格子中寻找和某些圆相交的点，这些圆的半径是：
在这个例子中，目标的格子中没有任何点，所以我们需要检查邻近的三个格子。这个方法可能会带来潜在的性能下降，因为a大多数格子可能为空。b算法仍然需要查找大多数邻近格子。简而言之，将P划分到多个格子中并不是一个很高明的方法。
另外一种解决方案便是构建Voronoi图（Preparata和Shamos，1985），将平面划分成n个区域Ri（0≤i＜n），Ri的定义为“离pi最近的点集”。因此这个区域是能够根据情况扩展到所需的大小[1]。在一个二维平面中，这样的区域是一个多边形（在更高的维度，每个区域是一个n维的多面体）。图9-18b是使用图9-18a的点得到的Voronoi图。一旦这个结构构建起来，那么只需找到邻近的区域Ri就能找到最邻近点。平均情况下，构建Voronoi图需要O(n log n)的时间，但是实现起来却非常复杂。使用Voronoi图，寻找最邻近点只需要O(log n)。
图 9-18 划分格子和Voronoi图的两种方法在图9-19（a）中，我们使用kd树来表示图9-18的19个点。kd树顾名思义，是沿着坐标系统的垂直坐标轴，切分一个k维的平面。在接下来的讨论中，我们假设这棵树是基于二维平面的，但是我们也要注意，kd树可以扩展到任意高维。一棵kd树是一个递归的二叉树结构，其节点包含多个点以及一个坐标标记（x或者y），这个标记表示切分线。根节点表示矩形范围是[xlow=-∞,ylow=-∞,xhigh=+∞,yhigh=+∞]。通过点p1画一条垂直切分线V。左子树表示是V左边的区域，右子树表示右边的区域。通过点p2画一条水平切分线H，根节点的左子节点会根据这条分割线将V的左部切分成上下两个部分。根节点的左子节点表示的区域是[-∞,-∞,P1.x,+∞]，右子节点表示[p1.x,-∞,+∞,+∞]。这些区域都高效地嵌套在一起。我们看到一个祖先节点的区域完全包含其所有后代的区域。
当kd树被正确地构建起来之后，在第i层的节点表示的矩形区域是第i+1层节点表示的矩形区域的两倍。这个性质使得最邻近点算法（图9-20）能够以O(log n)的性能高效地查找目标点，因为它能够抛弃整棵不可能包含最近点的子树。在接下来的“范围查询”一节中，我们将会看到这个实现是如何高效地进行范围查询的。
图 9-19 使用kd树切分二维平面 图 9-20 最近点查询详解输入/输出
输入
一个二维的点集P。一些最近点的查询（实现并不知道）。
输出
计算出一棵kd树。对于每个查询，计算在P中离x点最近的点。
假设
可能会有两个点非常近，在计算时会因为浮点的误差导致算法选择了错误的点，但是，由于这两个点如此接近，所以不会对结果产生致命的影响。
[1]在Voronoi图中，凸包上的区域是“开口”的，直到遇到图的边界，而内部节点的区域面积有限。