algorithm - 一组圆的边界圆

Question

我正在尝试用 Java 实现以下内容。

给定不同大小(可能)和位置的圆列表，确定一个大圆(位置和大小)，它刚好包围所有圆。

public class Circle {
    public int x, y, radius;
}

有什么想法吗？

Answer 1

miniball-of-balls 问题 已在 "The smallest enclosing ball of balls: combinatorial structure and algorithms" 中进行了研究， 例如。这项研究的一个成果是至少有一些算法(如 Welzl 算法)不能轻易地从点推广到球。

上述论文提出了一个O(n)算法来计算一组球的迷你球(n 是输入球的数量，即2D)。 Computational Geometry Algorithms Library (CGAL) 中提供了其 C++ 实现. (您不需要使用所有 CGAL；只需提取所需的头文件和源文件即可。)

注意:我是上述论文的合著者，也是 CGAL Min_sphere_of_spheres 包的作者。