Классическая задача: для конечного множества точек P ⊂ R^2 найти наименьшую по радиусу окружность, содержащую все точки (minimum enclosing circle, MEC / smallest enclosing circle). Ниже сравнение трёх подходов: чисто геометрические рассуждения (опорные точки), аналитическая оптимизация в координатах и алгоритмические методы (в частности алгоритм Уэлца). Для каждого — идея, преимущества, ограничения, сложность и практические замечания.

Общие свойства (важно для всех подходов)

Опорных (support) точек не более 3. Центр наименьшей окружности определяется либо парой точек (диаметр — две противоположные точки), либо тройкой невырожденных точек (их описанная окружность). Если все точки совпадают или лежат на одной точке/отрезке/прямой, поддержка ≤2.Достаточно рассматривать только вершины выпуклой оболочки P (h = число вершин). Сначала можно вычислить convex hull: O(n log n), затем работать с h точками (часто h ≪ n).

1) Геометрические рассуждения о опорных точках (комбинаторный / переборный подход)
Идея:

Перечислить все возможные кандидаты окружностей, задаваемые 1, 2 или 3 точками из P (на практике 2 и 3). Для каждой «кандидатной» окружности проверять, содержатся ли все точки внутри. Минимальная подходящая — ответ.

Варианты:

Наивный перебор трёх точек: O(n^4) (тройки O(n^3) × проверка всех точек O(n)). Можно оптимизировать, сначала по парам (диаметральные окружности) O(n^3) и т.д.С учётом выпуклой оболочки — перебор тройок/пар на hull: O(h^3 + n) или O(h^2 + n), что часто реально для небольшого h.

Плюсы:

Простая идея, простая и прозрачная реализация.Точные решения (при аккуратной работе с арифметикой).Подходит, если n небольшое или h невелик.

Минусы:

Плохая асимптотика для больших n/h.Надо аккуратно обрабатывать вырожденные случаи (коллинеарность трёх точек).Численная устойчивость при вычислении описанной окружности трёх почти коллинеарных точек.

Практические замечания:

Для пары точек окружность с ними на диаметре: центр — середина, радиус = расстояние/2.Для тройки точек центр — пересечение двух середин перпендикуляров; можно вычислить через решение 2×2 линейной системы или детерминантные формулы.Используйте допустимую погрешность eps для проверки «внутри» (<= r+eps).

2) Аналитическая оптимизация в координатах (возможности СОП/выпуклой оптимизации)
Идея:

Ввести переменные c = (cx, cy) — центр и r ≥ 0 — радиус. Задача:
minimize r
subject to ||p_i − c|| ≤ r, i = 1..n.Функция f(c) = max_i ||p_i − c|| — выпуклая. Это выпуклая оптимизационная задача (минимизация максимальной нормы), её можно решать средствами выпуклой оптимизации: субградиентные методы, второпорядковые методы, или явная формулировка как SOCP (second-order cone program).

Плюсы:

Подходит, если вы уже используете оптимизационные библиотеки (cvx, CVXOPT, MOSEK, ECOS и пр.) — легко формализовать и решать.Гарантии выпуклой оптимизации: глобальный минимум.Хорошо масштабируется для больших n с мощными оптимизаторами; можно включать дополнительные ограничения (встраивать задачу в более общую модель).

Минусы:

Для простейшей задачи специализированные геометрические алгоритмы обычно быстрее и проще.Необходима зависимость от численных оптимизаторов (или реализовать собственный метод).Потенциальные численные проблемы при очень точных требований; требуется аккуратный подбор параметров solver’a.Интерфейс и формат решения (точность, скорость) зависят от выбранного метода.

Сложность:

Теоретически задача сводится к одному выпуклому оптимуму; сложность зависит от выбранного solver’а. Практически многократно быстрее чем O(n^3) при использовании эффективных SOCP-солверов, но не даёт простой «встроенной» O(n) гарантии как Welzl.

Практические варианты:

Решить через SOCP: для всех i добавить конусную неравенство ||p_i − c||_2 ≤ r.Или минимизировать r^2 (производная более гладкая), но учтите, что (||p_i − c||_2)^2 ≤ r^2 даёт неявное (не совсем выпуклое) сравнение; лучше оставить норму с эпиграфом.Можно использовать субградиент/скользящую проекцию над c: минимизация f(c)=max_i ||p_i − c||.

3) Алгоритмические методы (Welzl’а, Miniball и др.)
Ключевой метод: Welzl’s randomized incremental algorithm
Идея:

Рекурсивно строим MEC для первых k точек с ограничением, что некоторый набор R (|R| ≤ 3) обязателен на границе решения. Алгоритм перемешивает точки случайнымно, добавляет по одной; если новая точка внутри текущей окружности — пропустить; если снаружи — рекурсивно пересчитываем MEC, добавляя эту точку в R. По сути это “randomized incremental” с ограничением размера R ≤ 3.

Свойства:

Ожидаемое время O(n) (линейно) на плоскости; память O(1) дополнительная (рекурсивный стек).Реализация компактна и понятна (несколько десятков строк кода).На практике очень быстра и стабильна.

Плюсы:

Простая реализация, очень быстрое в среднем.Нет необходимости в сторонних библиотеках.Линейное ожидаемое время, хорошо работает на больших данных.Можно сначала уменьшить набор до вершин выпуклой оболочки, тогда сложность по h.

Минусы:

Это рандомизированный алгоритм: гарантия линейного времени в ожидании; худший случай теоретически хуже (но в практике крайне маловероятен).Требуется аккуратная реализация вычисления окружности через 2/3 точек и корректная работа с погрешностями.Для абсолютной гарантии детерминированной линейной сложности придётся использовать сложные алгоритмы (Megiddo, Chan), которые значительно сложнее в реализации.

Альтернативы / готовые реализации:

Miniball (T. Gärtner): промышленно надёжная реализация «микрошара» (miniball) основана на тех же идеях, эффективна и тщательно отлажена.CGAL, Boost.Geometry и другие библиотеки имеют реализации MEC или соответствующие утилиты.

Сложность реализации:

Welzl: код ~50 строк, требуется определить функции для окружности через 0/1/2/3 опорных точек; аккуратная работа с числовой погрешностью.Miniball/Gärtner: готовые библиотеки, просты в использовании.

Сравнение и рекомендации

Если нужна быстрая, простая и надёжная реализация для практических задач — Welzl (или готовая Miniball) обычно лучший выбор. Линейное ожидаемое время, простота кода, достаточно устойчив на практике.Если у вас очень большое множество и вы заранее можете сократить до выпуклой оболочки — сначала вычистите hull (O(n log n)), затем запустите Welzl на h точках; в часто встречающихся случаях h ≪ n это лучший путь.Если вы хотите строгих теоретических детерминированных гарантий по времени — существуют сложные детерминированные алгоритмы линейного времени (Megiddo, и др.), но они трудны в реализации и редко нужны на практике.Если MEC — часть более общей выпуклой/оптимизационной задачи или вы уже используете оптимизационные solvers — решать как SOCP удобно. Хороший выбор, когда задача встроена в оптимизацию с другими ограничениями.Для очень маленьких n или для образовательных целей — простая проверка всех пар/троек достаточна и проще всего реализуется.

Численная стабильность и точность

Везде нужно задавать eps при сравнениях (проверка «точка внутри окружности»).При вычислении описанной окружности трёх точек лучше решать линейную систему в нормализованной форме и проверять близость к коллинеарности; для абсолютной точности можно использовать рациональную/многоразрядную арифметику или библиотеку с exact predicates (CGAL).В реализациях на float/double обычна практика: shuffle input, use tolerance ~1e-12…1e-9 в зависимости от масштаба.

Краткая таблица (резюме)

Перебор пар/троек (геометрический): прост в реализации, O(n^3) (или O(h^3)), подходит для маленьких n/h.Аналитическая (SOCP / выпуклая оптимизация): гибок, мощен в контексте общего оптимизационного решения, требует solver’а, скорость зависит от solver’а; гарантированная глобальная оптимизация.Welzl / Miniball (алгоритмический подход): ожидаемое O(n) время, компактная реализация/готовые библиотеки, лучший практический выбор для большинства задач.

Если хотите, могу:

Привести краткий псевдокод алгоритма Уэлца и формулы для вычисления описанной окружности по трём точкам;Подсказать готовую реализацию на C++/Python или показать, как сократить задачу до hull + Welzl.