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

如果近似解没问题，您可以尝试简单的优化算法。下面是一个示例，在 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 所指出的那样。

对于这个问题，有一个精确的、非迭代的算法;正如 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 的坐标。