最小化的点的最大曼哈顿距离的点的集合 [英] Minimize maximum manhattan distance of a point to a set of points

问题描述

有关3个2D：

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

我需要找到一个点 P（X，Y），使得曼哈顿距离的最大值

I need to find a point P(x,y), such that the maximum of the manhattan distances

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

将是最小的。

will be minimal.

任何有关算法思想？

我真的preFER一个确切的算法。

I would really prefer an exact algorithm.

推荐答案

有一个精确的，非迭代算法的问题;作为Knoothe指出，的曼哈顿距离是旋转相当于切比雪夫距离以及P是平凡可计算为切比雪夫距离作为平均极端的坐标。

There is an exact, noniterative algorithm for the problem; as Knoothe pointed out, the Manhattan distance is rotationally equivalent to the Chebyshev distance, and P is trivially computable for the Chebyshev distance as the mean of the extreme coordinates.

该点从P中的曼哈顿距离x内到达形成围绕钻石P.因此，我们需要找到一个封闭所有点的最小的钻石，它的中心会为P。

The points reachable from P within the Manhattan distance x form a diamond around P. Therefore, we need to find the minimum diamond that encloses all points, and its center will be P.

如果我们通过45度旋转的坐标系，钻石是正方形。因此，该问题可减小到找到的点的最小包围平方

If we rotate the coordinate system by 45 degrees, the diamond is a square. Therefore, the problem can be reduced to finding the smallest enclosing square of the points.

最小包围广场的中心，可以发现的最小外接矩形的中心（这是平凡计算为坐标的最大值和最小值）。还有就是最小包围广场无限多的，因为你可以转移中心沿最小矩形的短边，仍然有一个最小的封闭广场。对于我们而言，我们可以简单地用一个其中心与外接矩形一致。

The center of a smallest enclosing square can be found as the center of the smallest enclosing rectangle (which is trivially computed as the max and min of the coordinates). There is an infinite number of smallest enclosing squares, since you can shift the center along the shorter edge of the minimum rectangle and still have a minimal enclosing square. For our purposes, we can simply use the one whose center coincides with the enclosing rectangle.

所以，在算法形式：

1. 旋转和坐标系通过分配X'= X / SQRT（2） - Y / SQRT（2）中，y'=缩放的x / SQRT（2）+ Y / SQRT（2）
2. 计算x'_c =（最大（x'_i）+分钟（x'_i））/ 2，y'_c =（最大（y'_i）+分钟（y'_i））/ 2
3. 旋转回来x_c = x'_c /开方（2）+ y'_c /开方（2），y_c = - x'_c /开方（2）+ y'_c /开方（2）

然后x_c和y_c给P的坐标。

Then x_c and y_c give the coordinates of P.

这篇关于最小化的点的最大曼哈顿距离的点的集合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！