对于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度的坐标系中，钻石是一个正方形。 因此，该问题可减小到找到的点的最小包围的正方形。
一个最小包含正方形的中心，可以发现作为最小包围矩形的中心（其被平凡计算的坐标的最大值和最小值）。 有最小的封闭广场无限多的，因为你可以转移沿最小长方形的短边的中心，仍然有一个最小的封闭方形。 对于我们而言，我们可以简单地使用，其中心与外接矩形一致的人。
所以，在算法形式：
- 旋转，并通过分配X标尺的坐标系 '= X / SQRT（2） - Y / SQRT（2）中，Y'= X / SQRT（2）+ Y / SQRT（2）
- 计算x'_c =（MAX（X'_I）+分钟（X'_I））/ 2，y'_c =（MAX（Y'_I）+分钟（Y'_I））/ 2
- 旋转回到与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）和（0100）。 如果我们挑最分离点的平均值，这将产生（10,5）的第一个例子，如果我们把中间这将是（0,1），对第二个例子，这既具有较高的最大曼哈顿距离比最佳。
更新：貌似独立求解x和y，并采取最远点的平均值是实际可行的，前提是一个做一些预处理和后处理，如指出thiton 。
文章来源: Minimize maximum manhattan distance of a point to a set of points
