将点的最大曼哈顿距离最小化为一组点

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所指出的那样,曼哈顿距离在旋转上等于切比雪夫距离,而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的坐标.