覆盖2D平面上给定点的最小圆

Question

问题:在2D平面上覆盖给定N个点的圆的最小可能直径是多少？

什么是解决此问题的最有效算法,它是如何工作的？

Answer 1

这是最小的圆圈问题.请参阅参考资料以获取建议算法的链接.

E.Welzl,最小的封闭盘(球和椭圆体),在H. Maurer(编辑),新结果和计算机科学的新趋势,计算机科学讲义,卷.555,Springer-Verlag,359-37(1991)

是"最快"算法的参考.

Answer 2

对于最小的封闭球问题,有几种算法和实现.

• 对于2D和3D,Gärtner的实施可能是最快的.

• 对于更高的维度(比如说高达10,000),请查看https://github.com/hbf/miniball,这是Gärtner,Kutz和Fischer的算法实现(注意:我是其中一个-authors).

• 对于非常非常高的维度,核心集(近似)算法将更快.

注意:如果你正在寻找一种算法来计算最小包围球的球体,你会发现在C++实现计算几何算法库(CGAL) .(您不需要使用所有CGAL;只需提取所需的头文件和源文件.)