Постановка. Пусть на плоскости заданы точки $x_1,\dots ,x_n\in {\mathbb{R}}^2$. Нужно найти точку $P\in {\mathbb{R}}^2$, минимизирующую максимум евклидовых расстояний до данных точек:
$$\underset{P\in {\mathbb{R}}^2}{\min }f(P),f(P)=\underset{1\le i\le n}{\max }\Vert P-x_i\Vert .$$ Это классическая задача «минимального охватывающего круга» (1‑center, smallest enclosing circle). Ниже — существование, единственность, геометрическая характеристика и методы для частных случаев.
1) Существование и общие свойства
- Функция $f(P)$ непрерывна и выпукла; из того, что для $\Vert P\Vert \to \infty$ значение $f(P)\to \infty$, следует, что минимум достигается на некотором компактном множестве (например, внутри выпуклой оболочки точек плюс радиус). Следовательно, решение существует.
- Минимальный охватывающий круг определяется радиусом $r^{\ast }=f(P^{\ast })$ и центром $P^{\ast }$. В оптимуме на границе круга находятся не более трех опорных точек (support points). То есть существует подмножество из 2 или 3 точек, расстояние от которых до $P^{\ast }$ равно $r^{\ast }$, и весь набор содержится в этот круг.
- Для конечного множества точек в плоскости минимальный охватывающий круг единственен (его центр единственен). (Интуитивно: если два разных круга имели бы одинаковый наименьший радиус, их пересечение даёт круг меньшего радиуса или противоречие с поддержкой ≤3.)
2) Геометрическая характеристика (критерии)
- Если оптимальный круг опирается на две точки $a,b$ (т.е. лишь две точки на границе), то они образуют диаметр: центр $P^{\ast }=(a+b)/2$, радиус $r^{\ast }=\Vert a-b\Vert /2$.
- Если опирается на три точки $a,b,c$ (они не коллинеарны), то $P^{\ast }$ — окружность, проходящая через эти три точки (ее описывающий центр — пересечение перпендикулярных биссектрис). Радиус — окружность через эти три точки (circumradius). Точки, определяющие круг, образуют треугольник, центр которого не лежит вне треугольника (в частности для острого треугольника центр — описанный центр; для тупого треугольника оптимум определяется парой крайних точек).
- Следствие для трёх точек: для $n=3$ решение легко описывается:
- Если треугольник острый, $P^{\ast }$ — описанный центр (circumcenter).
- Если треугольник прямой или тупой, $P^{\ast }$ — середина наибольшей стороны, $r^{\ast }=$ половина длины наибольшей стороны.
- В общем случае поддержка имеет размер ≤3: оптимальный круг либо задаётся диаметральной парой самых отдалённых надуктих, либо тройкой точек, образующих описанную окружность.
3) Частные случаи и методы вычисления
- n=3:
- Вычислить длины сторон; если самая большая сторона имеет квадрат больше суммы квадратов двух других — треугольник тупой → центр — середина наибольшей стороны, иначе центр — пересечение перпендикулярных биссектрис (описанный центр). Практически: решить систему линейных уравнений для пересечения биссектрис.
- Формула (алгоритмически): решить для $P=(x,y)$ $$\Vert P-a\Vert =\Vert P-b\Vert =\Vert P-c\Vert$$ или пересечение двух уравнений $\Vert P-a{\Vert }^2=\Vert P-b{\Vert }^2$ и $\Vert P-a{\Vert }^2=\Vert P-c{\Vert }^2$.
- n=4:
- Сначала уменьшите задачу до выпуклой оболочки точек (только граничные точки могут быть опорными). Пусть на оболочке $m$ точек ($m\le 4$).
- Можно перебрать все варианты опорных множеств: все пары $(i,j)$ (центры — середины) и все тройки $(i,j,k)$ (вписать описанный центр), для каждого варианта вычислить центр и радиус и проверить покрытие всех точек; выбор с минимальным радиусом — ответ. Сложность перебора $O(m^3)$ с проверкой расстояний $O(n)$ (в простейшей реализации).
- Практически: часто либо пара диаметральных точек, либо тройка на окружности; алгоритм перебора тривиален для n=4.
- Общее n:
- Уменьшение до выпуклой оболочки: опорные точки лежат на оболочке, так что сначала вычислите оболочку за $O(n\log n)$.
- Наиболее эффективные алгоритмы:
- Welzl's randomized incremental algorithm — ожидаемое время $O(n)$, простой и широко используемый.
- Алгоритмы на базе LP‑type problems дают ожидаемое линейное время; существуют и детерминированные алгоритмы с линейной или $O(n\log n)$ сложностью, но более сложные в реализации.
- Прямое решение как выпуклая оптимизация: минимизировать $r$ при ограничениях $\Vert P-x_i\Vert \le r$. Это SOCP (второго порядка конусная задача) или выпуклая задача, решаемая стандартными солверами за полиномиальное время.
- Простая детерминированная реализация: построить выпуклую оболочку, перебрать все пары и тройки точек оболочки (количество их обычно малое), вычислить соответствующие центры и выбрать минимальный приемлемый радиус; сложность в худшем случае $O(m^3+m\cdot n)$ но на практике быстро.
4) Практические замечания и формулы
- Центр для пары $a,b$: $P=(a+b)/2,r=\Vert a-b\Vert /2$.
- Центр для тройки вычисляют как пересечение перпендикулярных биссектрис или решением линейной системы для $P$ из уравнений $\Vert P-a{\Vert }^2=\Vert P-b{\Vert }^2$, $\Vert P-a{\Vert }^2=\Vert P-c{\Vert }^2$.
- Рекомендуемые подходы: для практики — реализовать Welzl (коротко и эффективно) или использовать библиотечный алгоритм (CGAL, scipy.spatial для ближайших задач и т.п.). Для формальной гарантии — SOCP‑решение через конвексные солверы.
Краткая сводка:
- Существование: да. Уникальность центра: да (для конечного множества). Поддержка ≤3.
- n=3: либо описанный центр (если острый), либо середина наибольшей стороны.
- n=4: редуцируйте к выпуклой оболочке, перебор пар и троек; практически то же, что и в общем случае.
- Общее n: Welzl — ожидаемое $O(n)$; альтернативно SOCP/L P‑type алгоритмы или перебор на выпуклой оболочке для практической реализации.