寻找(x,y)坐标之间的最大距离

Question

我试图计算一个大的2D输入的最大曼哈顿距离，输入由(x, y)对组成，我想要做的是计算这些坐标之间的最大距离。并且希望在小于O(n^2)的时间内完成。我可以通过遍历所有元素来使用O(n^2)来实现，类似于以下方式：
*(两点 (X1,Y1) 和 (X2,Y2) 之间的曼哈顿距离为：|X1-X2| + |Y1-Y2|)

for ( 0 -> n )  
   for ( 0-> n )   
       { // here i calculate |Xi - Xj| + |Yi - Yj| which is maximum }  

但是它在处理非常大的输入时效率不高 :(
有人有更好的算法吗？

- user633784

Answer 1

只有两种情况需要考虑，如果我们仅考虑结果使得Xi <= Xj。

• 如果Yi <= Yj，那么距离为(Xj + Yj) - (Xi + Yi)
• 否则，距离是(Xj - Yj) - (Xi - Yi)

通过将它分解成这些情况，我消除了绝对值函数，使得关于距离的推理变得更加容易。

因此，我们只需选择具有最小和最大x+y的点，并计算距离。然后选择具有最小和最大x-y的点，并计算距离。其中一个距离是您的最大距离。

这可以在O(n)的时间复杂度内完成，这是渐进最优的。

- Dietrich Epp

Answer 2

这很简单，可以在 O(n) 的时间复杂度内计算。

假设 x1>x2，且 y1>y2

max(|x1-x2|+|y1-y2|) = max(x1-x2+y1-y2) = max(x1+y1) - min(x2+y2)

假设 x1>x2, 且 y1<y2

max(|x1-x2|+|y1-y2|) = max(x1-x2-y1+y2) = max(x1-y1) - min(x2-y2)

现在将x1更换为x2，您将获得相同的结果。

因此，总的来说，您的解决方案是

max ( (max(xi+yi)-min(xi+yi)), (max(xi-yi) - min(xi-yi)) ) 

- pnezis

Answer 3

处理这种问题的最好方法是尝试建立一些小的结果，这些结果将有助于解决整个问题。例如，可以很容易地确定对于任何满足B在A和C之间（稍后再详细说明）的三个点A、B和C，B永远不会比A和C中的一个更远离第四个点D。使用标准欧几里得距离，如果一个点位于连接它们的线段上，则该点在两个其他点之间。对于曼哈顿测量来说，情况并不那么简单，部分原因是线段的概念没有被很好地理解。描述“在两点之间”的一种更一般的方式是这样的（使用从A到B的距离为|AB|的符号表示）：如果|AB| + |BC| = |AC|，则点B在点A和点C之间。您可以看到，在欧几里得距离中，这意味着B位于连接A和C的线段上。在曼哈顿距离中，这意味着点B包含在由A和C定义的矩形中（当然，如果AC与其中一个轴平行，则可能是一个直线段）。这个结果意味着对于任何点，如果它位于两个现有点之间，它与添加到集合中的任何新点之间的距离都不会超过它所包围的两个点。现在，这些信息并不能为您解决问题，但是可以让您放弃许多潜在的未来计算。一旦确定一个点在两个其他点之间，就没有必要跟踪它了。因此，您可以通过仅跟踪最外层的点并忽略任何落在其中的点来解决此问题。使用曼哈顿距离，证明您最多只能有4个不同的点，使得这些点中没有一个在另外两个点之间。通过第二个结果，可以清楚地看到您将只需要跟踪最多4个点。已经提出的其他一些方法可能更快，但是这种方法更有趣！将这些想法推广到n维。

- Cogito

Answer 4

第一个重大改进将是：

for ( X: 0 -> n )
    for ( Y: X -> n )
        { compute the distance between X and Y }

因为X和Y之间的距离与Y和X之间的距离相同。这将使您的计算减少一半...

- Adrien Plisson

---

是的，这是一个改进，但仍然需要O(n^2)的时间:(对于非常大的输入不起作用。 - user633784

是的，我知道，我只是指出了第一个明显的改进：减少比较的数量仍然是一个非常大的改进。我还在考虑更快的方法... - Adrien Plisson

Answer 5

最大距离将在最远点之间。因此，您只需找到具有最大X和最大Y的点，然后找到具有最小X和最小Y的点，并计算它们之间的距离。 可能会有很多符合条件的点..但至少您将有更少的点要检查

- Vitaly Dyatlov

---

不行，因为具有最大X坐标的点，可能没有最大的Y坐标！最小值也是如此，请考虑这些：（7，-2），（-1，5），（3，-9）等等，这三个将驳斥您的算法。 - user633784