涉及“最小圆问题”的计算机图形相关任务

Question

我有两个与“最小圆问题”相关的任务：

1. 实现一次性算法，计算一组通用 2D 点的外接圆。
2. 为算法定义一组 2D 点 Q，该算法返回一个大于最小圆的封闭圆。

我已经使用 Welzl 算法完成了任务#1；但我不确定我是否理解了第二个问题。他们是要我找到算法的破解方法，还是算法的局限性？

Answer 1

第一个任务不是要求算法来找到最小包围圆，而是要求算法来找到an包围圆。它指定这应该是“一次性”算法，这意味着该算法仅在点列表上迭代一次。

第一个任务有很多可能的答案，因为它并没有限制你可以画多大的圆圈；例如，如果集合仅包含一个点，则算法找到包含该点的半径为 10²⁰ 的圆是完全有效的。 （当然，没有理由走得这么极端。如果最小外接圆的半径是R，有一个非常简单的一次性算法来找到半径最大为R√2的外接圆，其中我会在下面添加一个剧透标签，以便您可以先考虑一下。）

迭代点，跟踪最小和最大 x 坐标以及最小和最大 y 坐标。返回圆心 = (½(x_min + x_max), ½(y_min + y_max)) 和半径 = ½√((x _max − x_min)² + (y_max − y_min)²)。

第二个任务取决于您对第一个任务的回答。由于您的算法可能无法找到所有点集的最小外接圆（因为我们不知道有任何单遍算法可以做到这一点），因此第二个任务只是找到您的点集算法返回比需要的更大的圆。例如，如果对于任务#1，您使用上面剧透中描述的算法，那么对于任务#2，您可以给出

集合{(1, 0), (0, 1), (-1, 0), (0, -1)}：最小外接圆的半径为1，但上面的算法给出了半径为√2的圆.