求解二维平面内到给定点集最大欧氏距离最小的点：拆分坐标轴方法失效问题

1. 优化目标完全不等价 #

你要解决的问题是最小化所有点到目标点的欧氏距离的最大值，也就是遍历点集中所有点，取每个点到候选点的欧氏距离的最大值，找到让这个最大值最小的候选点。由于平方根是单调递增函数，该问题等价于最小化所有点到候选点的「x坐标差的平方加y坐标差的平方」的最大值。

而你的拆分做法是独立求解两个一维问题：

• x轴方向最小化max(|x - x_i|)，最优解为所有x坐标的最小值和最大值的中点：x_opt = (min x_i + max x_i) / 2
• y轴方向最小化max(|y - y_i|)，最优解为所有y坐标的最小值和最大值的中点：y_opt = (min y_i + max y_i) / 2

这两个一维问题对应的是切比雪夫距离（L∞范数）下的最小最大点的求解目标，和欧氏距离（L2范数）的优化目标没有等价性。

2. 维度耦合性被完全忽略 #

欧氏距离的x分量和y分量是耦合的：你为了缩小y方向的最大差值选择的y值，可能会导致部分点的x差平方与y差平方的总和升高，反而增大了整体的最大欧氏距离。

举个直观反例：给定点集{(0,0), (4,0), (0,2), (1,3)}

• 按你的拆分法计算：x坐标范围0_{4，得x=2；y坐标范围0}3，得y=1.5，对应点(2,1.5)，到所有点的最大距离为2.5。
• 实际最优解为(2,1)，到所有点的最大距离约为2.236，远小于拆分法的结果。这个解的y方向最大差值（2）比拆分法的1.5更大，但整体欧氏距离反而更小，就是因为维度耦合的影响。

部分测试用例结果正确的原因是，当最小包围圆恰好由x方向极值点或y方向极值点构成时，拆分法的输出会恰好和正确解重合，但这是巧合，不具备通用性。

你要找的点本质上是平面点集的最小包围圆（MEC）的圆心——半径最小的能覆盖所有给定点的圆，其圆心就是到所有点最大欧氏距离最小的位置。

核心性质 #

平面最小包围圆是唯一确定的，且最多由点集中的2个或3个点唯一确定：

• 若由2个点确定：这两个点是圆的直径端点，圆心为两点的中点。
• 若由3个点确定：这三个点都在圆周上，圆心为三点构成三角形的外心（三边垂直平分线的交点）。

常用实现方法 #

• 小规模点集：枚举所有2点组合、3点组合，计算对应圆的半径，检查是否能覆盖所有点，取半径最小的圆即可。
• 大规模点集：使用Welzl随机增量算法，期望时间复杂度为线性，是目前该问题的主流高效实现方案。
• 通用优化解法：该问题属于凸优化范畴，可以转化为二阶锥规划（SOCP）问题直接调用优化器求解，适配任意规模的点集。

内容的提问来源于stack exchange，提问作者maria maria