在二维空间中找到两个最远的点（曼哈顿距离）

Question

在二维空间中给定点的列表(x[i], y[i])，我们需要找到两个最远的点(曼哈顿距离)。

我知道这个算法，但我不太明白它是如何工作的。

1. 找到以下点：max(x[i] + y[i])、max(-x[i] + y[i])、max(-y[i] + x[i])和max(-x[i] - y[i])，其中i为所有点。

2. 计算列表中每个点与上一步选择的四个点之间的距离，并选择最大值。

请有人解释一下为什么这个算法是正确的。

- Raman

Answer 1

我们需要最大化曼哈顿距离，其中P=(X,Y)是来自该集合的任意固定点。

MD = Abs(X - x[i]) + Abs(Y - y[i])

有四种情况：

1. 最远的点在 P 左下方（不严格满足条件，x[i]<=X, y[i]<=Y），所以我们可以打开绝对值括号，变成

MD =  X - x[i] + Y - y[i]

当(-x[i] - y[i])最大时，该表达式的最大值被达到。

2. 最远的点在P的左上方，因此

MD =  X - x[i] - Y + y[i]

这个表达式的最大值是当(-x[i] + y[i])最大时达到的。

右上和右下情况同理。

因此，我们可以看到，对于任何属于集合的P点，最远的点必须从这四种变体中选择（称为极点）。

重新表述：

如果我们从集合中选择任何点P，则距离最远的点是极点E。但是，从极点到最远点的距离也是极点E1 - 也就是说它可能是P，如果P是极点的话。

- MBo

---

没错，如果我们将坐标系“移动”到 P = (0,0)，事情可能会变得更容易理解。 - Ta Thanh Dinh

Answer 2

假设 P1 = (x1, y1) 和 P2 = (x2, y2)，使得 d(P1, P2) = |x1-x2| + |y1-y2| 最大。

例如，假设 x1 >= x2 并且 y1 >= y2（其他情况类似，您需要使用其他最大点）。则：

d(P1, P2) = x1 - x2 + y1 - y2 (1)

假设 P3 = (x3, y3) 且 x3 + y3 最大。我们的目标是证明 d(P3, P2) >= d(P1, P2)。

根据定义，x3 + y3 >= x1 + y1 (2)。结合 (1) 和 (2)：

• 如果 x3 <= x2，则：d(P3, P2) = x2 - x3 + y3 - y2 >= x2 - x3 + (x1 + y1 - x2) - y2 = x1 + y1 - x3 - y2 >= x1 - x2 + y1 - y2 = d(P1, P2)
• 如果 y3 <= y2：对称的情况。
• 否则 x3 >= x2 且 y3 >= y2： d(P3, P2) = x3 - x2 + y3 - y2 >= x1 - y2 + y1 - y2 = d(P1, P2)。

因此，d(P3, P2) >= d(P1, P2) 且 d(P3, P2) <= d(P1, P2)，故该算法在此情况下是正确的。

几何证明：我们将所有点移动，使得 P2 现在是 (0, 0)。然后该集合的直径就是到一个最大直径闭球上的点的距离。曼哈顿距离下的球是方形，其边缘与坐标轴成 pi/4 角度。在这种情况下，公式很容易找到（它只取决于最大距离点位于哪个象限）。

- md5

Answer 3

我不能给你一个超级技术性或详细的答案，但直觉上讲，这是有道理的。

你首先找到角点的原因是因为两个点之间的最大曼哈顿距离总是包括一个角点。如果不包括，则只能等于或更小。这使得对于大型数组，您不必搜索每个组合，因此您的搜索将更加高效。如果需要帮助来形象化它，那么请想象一个图上的6个点。想象一下四个角点在任何可能的位置。然后尝试想象一种方式，其中内部的两个点比任何具有角点的点都要远。希望这可以帮助到你。我知道这不是非常技术性的。

- Henry