Контрпример (и разбор ошибки).
Пример. Возьмём равнобедренный треугольник с вершинами
$A=(0,\frac{1}{\sqrt{3}})$, $B=(-1,0)$, $C=(1,0)$.
Угол при вершине $A$ равен $120^{\circ }$. Центроид (точка пересечения медиан)
$$G=\frac{A+B+C}{3}=(0,\frac{1}{3\sqrt{3}}).$$
Рассмотрим задачу: найти точку $P$ минимизирующую сумму евклидовых расстояний до вершин,
$$S(P)=|PA|+|PB|+|PC|.$$
Очевидная (ошибочная) эвристика: «центроид минимизирует сумму расстояний». Покажем, что это не так.
Вычисления:
- если взять $P=A$, то
$|PA|=0,|PB|=|PC|=\sqrt{1+\frac{1}{3}}=\frac{2}{\sqrt{3}}$,
поэтому
$$S(A)=0+2\cdot \frac{2}{\sqrt{3}}=\frac{4}{\sqrt{3}}\approx \mathrm{2.3094.}$$
- для центроида $G$:
$|GA|=\frac{2}{3\sqrt{3}}\approx 0.3849,|GB|=|GC|=\sqrt{1+\frac{1}{27}}=\sqrt{\frac{28}{27}}\approx 1.0184,$ поэтому
$$S(G)=|GA|+|GB|+|GC|\approx 0.3849+2\cdot 1.0184\approx \mathrm{2.4217.}$$
То есть $S(G)>S(A)$. Следовательно центроид не даёт минимума суммы расстояний — оптимум достигается в вершине $A$.
Почему эвристика вводит в заблуждение и как правильно подходить
- Центроид действительно минимизирует сумму квадратов расстояний:
$$\Phi (P)=|PA{|}^2+|PB{|}^2+|PC{|}^2$$ и критическая точка $\nabla \Phi =0$ даёт $P=\frac{A+B+C}{3}$. Но это другое функциональное требование (квадраты вместо модулей).
- Для функционала $S(P)=\sum |P-V_i|$ условие стационарности (при $P$ не совпадающем с вершиной) векторно:
$$\sum _{i=1}^3\frac{P-V_i}{|P-V_i|}=0.$$ Для треугольника с углами < $120^{\circ }$ это ведёт к точке Ферма (Торричелли), из которой лучи к вершинам образуют углы $120^{\circ }$. Если в треугольнике есть угол $\ge 120^{\circ }$, то оптимум достигается в соответствующей вершине (как в нашем примере).
- Правильный алгоритм решения:
1. Проверить, есть ли угол треугольника $\ge 120^{\circ }$. Если да — оптимум в этой вершине.
2. Иначе искать точку Ферма: использовать геометрическую конструкцию (строить внешние равносторонние треугольники и соединять соответствующие вершины) или численные методы (напр., алгоритм Вайцфельда для геометрической медианы или решение системы $\sum (P-V_i)/|P-V_i|=0$).
Краткий вывод: центроид — это центр масс и минимизатор суммы квадратов расстояний, но не оптимизатор суммы модулей расстояний; для последней задачи нужно проверять углы и применять критерий Ферма/геометрической медианы.