<分区>
一道数学题我已经被困了几天了。
给定二维平面上的一组点(超过 11 个)，找出不包含超过 11 个点的最大圆。
显而易见的方法是获取大小为 12 的所有可能子集，然后为每个子集找到最小外接圆，但这将花费太长时间来计算。
关于更有效的方法有什么想法吗？
<分区>
一道数学题我已经被困了几天了。
给定二维平面上的一组点(超过 11 个)，找出不包含超过 11 个点的最大圆。
显而易见的方法是获取大小为 12 的所有可能子集，然后为每个子集找到最小外接圆，但这将花费太长时间来计算。
关于更有效的方法有什么想法吗？
最佳答案
我怀疑存在一个完全不切实际的 O(n log n) 时间算法，它计算 order-12 (!) Voronoi 图并像 O(n log n) 时间算法一样进行最大空圆。实际上，每个可行的圆是由输入点中的三个(在边界上)或两个(作为直径)确定的。天真地尝试所有这些都是四次时间，但对于每对点 P 和 Q，线 PQ 一侧的点相对于圆上方的其他点所包围的点是完全有序的，下面的点也是如此。这种洞察使我们通过排序得到 n^3 log n；使用选择算法应该可以实现二次。
关于algorithm - 包含不超过 11 个点的最大圆，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21518980/