使用曼哈顿距离的最近点对

Question

我正在学习CLR中的一节，它描述了使用分而治之的方法，使用两点之间的欧几里德距离来找到最近的点对。

有一个问题，要求找到最近的点对之间的manhatten距离，使用类似的方法。但是，我不能把握两者之间的区别。以下是我能想到的：

3）递归到我们的点子集<=3为止（在这种情况下使用蛮力）

4）最小距离可以是从任何一个递归调用返回的距离--称它为D。

5）找到线“L”周围2D宽度内所有点，然后对于每个这样的点，找到它与条带内（所有？？）个点的manhatten距离？

更具体一点：CLR中提到，对于欧几里得距离，我们只需要检查7个点，而在谷歌上搜索后，这个参考指出，对于曼哈顿距离，我们需要考虑12个点。我无法理解这种逻辑，这种点的选择是如何依赖于我们所寻求的距离类型的。

Answer 1

对于L的左侧部分的每个点，右侧至多有6个点与之的距离小于d。这6个点可以定位在两个方块的六个角上。再多一个，就可以找到距离小于d的一对。

然后对L右侧的点按Y坐标排序。找到在y轴上最接近P的6个点，这可能产生更近的距离。