这就是所谓的最小封闭球问题(在你的情况下,最小的封闭圆圈),又名迷你球.这个问题有几种算法和实现 - 以下所有都是线性时间解决方案(即,给定n个球,如果你认为维度d是固定的,它们在O(n)中运行,在你的情况下d = 2) :
对于2D和3D,Gärtner的实施可能是最快的.
对于更高的维度(比如说高达10,000),请查看https://github.com/hbf/miniball,这是Gärtner,Kutz和Fischer的算法实现(注意:我是其中一个-authors).
对于非常非常高的维度,核心集(近似)算法将更快.
注意:如果你正在寻找一种算法来计算最小包围球的球体,你会发现在C++实现计算几何算法库(CGAL) .(您不需要使用所有CGAL;只需提取所需的头文件和源文件.)