Nearest Neighbor - 最近点对
问题
求出二维平面坐标系上个点中最近两点的距离。
解法
遍历所有顶点求出任意两点间的距离，从而求出最近距离，该方法的时间复杂度为，本文介绍一个更快的算法。
通过分治法将二维平面坐标系上的个顶点作为一个区域，可知该区域的坐标范围为，坐标范围为。如下图所示：
在区域中选取坐标最接近的顶点（若存在多个相同坐标的顶点，选择轴最小的），用垂直于轴，坐标为的直线将该区域划分为左右两个子区域和。顶点不属于或任意区域。对两个子区域，类似的继续进行划分，直到区域中顶点的数量。
当一个区域中的顶点数量时，可以直接求出这些顶点中的最近两点距离。对于两个相邻子区域，虽然已知两个子区域内的最近两点距离，但两个相邻子区域合并后的最近两点距离仍然不确定。
当合并两个相邻子区域和时，设两个子区域的最近两点距离分别为，分割两个区域的中点为。对于区域中的任意顶点，若其满足
则与有可能是最近点对，不满足该条件的与必然不是最近点对。
通过直接判断轴可以避免计算二维平面上两点距离时的乘法运算，最终只需要计算出与它周围最近的的一部分顶点的距离即可。算出点与它周围顶点的距离。同理，对于区域中的所有满足下列条件的顶点：
点与这些顶点的距离为。在周围的顶点，以及区域中的最近点对，在这些点对中选出距离最近的两点。重复上述操作，递归合并相邻两区域，最终可以求出个点中的最近两点距离。
该算法的时间复杂度为。