Это так называемая проблема наименьших вмещающих шариков (в вашем случае, наименьший вмещающий круг ), также известная как Miniball .Существует несколько алгоритмов и реализаций для этой проблемы - все нижеприведенное является линейно-временным решением (т. Е. С учетом n шаров они работают в O (n) , если вы считаете,размер d фиксированный, d = 2 в вашем случае):
Для 2D и 3D, Реализация Гертнера вероятно самый быстрый.
Для более высоких измерений (скажем, до 10 000) взгляните на https://github.com/hbf/miniball,, который является реализацией алгоритма Гертнера, Куц,и Фишер (примечание: я один из соавторов).
Для очень и очень больших размеров алгоритмы core-set (приближение) будут быстрее.
Примечание: Если вы ищете алгоритм для вычисления наименьшей охватывающей сферы из сфер , вы найдете реализацию C ++ в Библиотека алгоритмов вычислительной геометрии (CGAL) .(Вам не нужно использовать весь CGAL; просто извлеките требуемый заголовок и исходные файлы.)