1

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

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

编辑：平面上的n个点，并且所有点都可以说-10^9 <= x,y <= 10^9。

4

1 回答 1

0

假设您正在谈论平面上的点，请在坐标中找到和n坐标的最小值和最大值。创建一个大小为x的矩阵，以便所有点都可以由矩阵中的一个单元格表示。用给定的点填充矩阵（例如，并非所有单元格都将被填充，设置在那里）。扫描矩阵 - 矩阵中相邻填充单元之间的最短距离（可能有几个这样的对）。xymaxX-minXmaxY-minYnNaN

于 2013-03-12T17:31:53.727 回答