曼哈顿距离的两个最近点

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

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

编辑：在一个平面上Ñ点，并且可以说-10^9 < = X，Y < = 10^9所有点。

2013-03-12 xan

http://stackoverflow.com/questions/13778044/finding-the-distance-between-two-sets-in-manhattan-distance – sukunrt 2013-03-12 18:33:39

假设您在飞机上谈论n点，请在坐标中查找最小值和最大值x和y坐标。创建一个大小为maxX-minX x maxY-minY的矩阵，使得所有点都可以由矩阵中的单元格表示。用给定的点填充矩阵（例如，不是所有的单元都将被填充，在那里设置为NaN）。扫描矩阵 - 矩阵中相邻填充单元之间的最短距离（可能有几个这样的对）。

来源

2013-03-12 17:31:53 SomeWittyUsername

对不起，我只是编辑了我的问题。可以说x，y足够大，所以我们不能创建这样的矩阵。 – xan 2013-03-12 17:38:17

有一些方法可以存储稀疏矩阵而不会浪费太多空间：http://en.wikipedia.org/wiki/Sparse_matrix – SomeWittyUsername 2013-03-12 17:43:49

曼哈顿距离的两个最近点

回答

相关问题