algorithm - 最小化一个点到一组点的最大曼哈顿距离

Question

对于 2D 中的 3 个点：

P1(x1,y1), 
P2(x2,y2), 
P3(x3,y3) 

我需要找到一个点P(x,y)，使得曼哈顿距离的最大值

max(dist(P,P1), 
    dist(P,P2), 
    dist(P,P3))

将是最小的。

关于算法的任何想法？

我真的更喜欢精确的算法。

Answer 1

这个问题有一个精确的、非迭代的算法；正如 Knoothe 所指出的，曼哈顿距离在旋转上等价于 Chebyshev 距离，并且对于 Chebyshev 距离，P 可以简单地计算为极端坐标的平均值。

在曼哈顿距离 x 内从 P 可到达的点形成围绕 P 的菱形。因此，我们需要找到包围所有点的最小菱形，其中心将为 P。

如果我们将坐标系旋转 45 度，菱形就是正方形。因此，问题可以简化为找到点的最小封闭正方形。

可以找到最小封闭正方形的中心作为最小封闭矩形的中心（通常计算为坐标的最大值和最小值）。有无数个最小的封闭正方形，因为您可以沿着最小矩形的较短边缘移动中心，并且仍然有一个最小的封闭正方形。出于我们的目的，我们可以简单地使用中心与封闭矩形重合的那个。

因此，以算法形式：

1. 通过指定 x' = x/sqrt(2) - y/sqrt(2), y' = x/sqrt(2) + y/sqrt(2) 来旋转和缩放坐标系
2. 计算 x'_c = (max(x'_i) + min(x'_i))/2, y'_c = (max(y'_i) + min(y'_i))/2
3. 旋转回来 x_c = x'_c/sqrt(2) + y'_c/sqrt(2), y_c = - x'_c/sqrt(2) + y'_c/sqrt(2)

然后 x_c 和 y_c 给出 P 的坐标。

Answer 2

如果一个近似的解决方案是好的，你可以尝试一个简单的优化算法。这是一个例子，在 Python 中

import random
def opt(*points):
    best, dist = (0, 0), 99999999
    for i in range(10000):
        new = best[0] + random.gauss(0, .5), best[1] + random.gauss(0, .5)
        dist_new = max(abs(new[0] - qx) + abs(new[1] - qy) for qx, qy in points)
        if dist_new < dist:
            best, dist = new, dist_new
            print new, dist_new
    return best, dist

解释：我们从点 (0, 0) 或任何其他随机点开始，并对其进行数千次修改，每次都保持新的和以前最好的点中的更好。逐渐地，这将接近最佳值。

请注意，在最小化最大曼哈顿距离时，简单地选择三个点的平均值或中位数，或独立求解 x 和 y 不起作用。反例：考虑点 (0,0)、(0,20) 和 (10,10)，或 (0,0)、(0,1) 和 (0,100)。如果我们选择最分离点的平均值，则第一个示例将产生 (10,5)，如果我们取中位数，则第二个示例将产生 (0,1)，两者都具有更高的曼哈顿最大值距离比最优。

更新：看起来像独立求解 x 和 y 并取最远点的平均值实际上确实有效，前提是要进行一些预处理和后处理，正如thiton所指出的那样。