Постановка. Пусть даны вершины выпуклого многоугольника $A_1,\dots ,A_n\subset {\mathbb{R}}^2$. Найти все точки $P\in {\mathbb{R}}^2$, минимизирующие сумму расстояний до вершин
$$f(P)=\sum _{i=1}^n|P-A_i|.$$
Общие свойства и условие оптимальности.
- Функция $f$ является суммой выпуклых функций, поэтому выпукла; следовательно множество минимизаторов выпукло и (при неналичии коллинеарности всех точек) минимум единственен.
- Необходимое и достаточное условие для внутренней точки $P$ (звено типа «градиент = 0»):
$$\sum _{i=1}^n\frac{P-A_i}{|P-A_i|}=0.$$ Это означает, что в точке минимума векторы единичных направлений к вершинам векторно компенсируются.
- Если оптимум достигается в одной из вершин, скажем $P=A_k$, то субградиентный критерий даёт условие
∣∑i≠kAk−Ai∣Ak−Ai∣∣≤1, \left|\sum_{i\ne k}\frac{A_k-A_i}{|A_k-A_i|}\right|\le 1,
i=k∑ ∣Ak −Ai ∣Ak −Ai ≤1, что эквивалентно тому, что нулевая векторная сумма может быть получена добавлением некоторого вектора длины не более 1 для слагаемого с модулем неопределённым в точке совпадения.
Частные случаи и сравнение.
1) Два пункта ($n=2$). Минимум на отрезке $A_1{A}_2$ достигается в середине. Формула: $P=\frac{A_1+A_2}{2}$.
2) Треугольник ($n=3$) — задача Ферма–Торричелли.
- Если в треугольнике есть угол $\ge 120^{\circ }$ (то есть $\ge 2\pi /3$), то точка минимума — соответствующая вершина.
- Если все углы $<120^{\circ }$, то существует единственная внутренняя точка $P$ (Ферма), такая что три отрезка $P{A}_i$ попарно составляют углы по $120^{\circ }$; аналитически это удовлетворяет
$$\sum _{i=1}^3\frac{P-A_i}{|P-A_i|}=0.$$ Геометрическая конструкция: на сторонах строят правильные треугольники и проводят соединяющие от вершины противоположные вершины — пересечение этих прямых есть точка Ферма (доказательство через поворот на $60^{\circ }$).
3) Квадрат и правильный многоугольник.
- Для квадрата (и для любого правильного $n$-угольника) по симметрии центр $O$ правильного многоугольника даёт стационарную точку и, ввиду выпуклости $f$, является единственным минимумом:
$$P=O.$$ - Для большого $n$ (правильный $n$-угольник) центр минимизирует сумму из-за симметрии; для равномерно расположенных точек центровая точка удовлетворяет векторному условию (векторы взаимно компенсируются).
Замечание: в общем случае выпуклого (но не регулярного) многоугольника геометрическая медиана обычно не совпадает с центроидом (ср. центр масс) и нет простых закрытых формул.
Методы доказательства оптимальности.
1) Геометрический (конструктивный): для треугольника используют поворот на $60^{\circ }$ или построение наружных равносторонних треугольников — показывает, что точка с углами $120^{\circ }$ минимизирует сумму. Для симметричных конфигураций (правильные многоугольники) симметрия даёт очевидную минимальную точку.
2) Аналитический: рассматривают функцию $f(P)$, её (суб)градиент. Для внутренней оптимальной точки необходимо и достаточно условие
$$\sum _{i=1}^n\frac{P-A_i}{|P-A_i|}=0.$$ Второй шаг — использовать выпуклость $f$ (глобальный минимум при исчезновении градиента). Можно также оценивать изменение при малом сдвиге $h$:
$$f(P+h)-f(P)=\sum _{i=1}^n\left(|P+h-A_i|-|P-A_i|\right)=\sum _{i=1}^n\frac{P-A_i}{|P-A_i|}\cdot h+o(|h|).$$
3) Вариационный и численный: применяют субградиентную теорию и численные алгоритмы (Weiszfeld):
$$P^{(t+1)}=\frac{{\sum }_{i=1}^n\frac{A_i}{|P^{(t)}-A_i|}}{{\sum }_{i=1}^n\frac{1}{|P^{(t)}-A_i|}}.$$ Weiszfeld сходится к геометрической медиане при корректной обработке случая, когда итерация попадает точно в одну из точек данных.
Краткие выводы.
- Минимizer суммы расстояний — геометрическая медиана; она единственна для ненаправленных конфигураций точек и удовлетворяет суммарному векторному условию.
- Для треугольника: либо внутренняя точка с углами $120^{\circ }$, либо вершина при угле $\ge 120^{\circ }$.
- Для квадрата и любых правильных $n$-угольников — центр по симметрии.
- Доказательства используют: чисто геометрические конструкции (треугольник), аналитические методы (субградиент/выпуклость) и вариационные/численные методы (Weiszfeld) для общего случая.