algorithm - 曼哈顿距离中最近的两个点

Question

我想知道曼哈顿距离。它非常具体，而且(我不知道这是一个好词)简单。例如，当我们在这个度量中得到一组 n 点时，那么很容易在线性时间内找到两个最远点之间的距离。但是找到两个最近的点也容易吗？

我听说，存在用于在任何度量中找到两个最近点的通用算法，但它很复杂。我想知道在这种情况下(曼哈顿度量)是否可以使用这个距离的特殊属性并提出一个更简单的算法，这将在实现中更友好？

编辑:n 点在平面上，假设所有点都为 -10^9 <= x,y <= 10^9。

Answer 1

假设你在谈论一个平面上的 n 点，在坐标中找到 x 和 y 坐标的最小值和最大值.创建一个大小为 maxX-minX x maxY-minY 的矩阵，这样所有点都可以由矩阵中的一个单元格表示。用给定的 n 点填充矩阵(例如，并非所有单元格都将被填充，在那里设置 NaN)。扫描矩阵 - 最短距离是矩阵中相邻填充单元格之间的距离(可能有几个这样的对)。