Геометрическая медиана и алгоритм Вайсфельда
Центроид (среднее арифметическое координат) легко считается, но он минимизирует сумму квадратов расстояний до точек. А нам нужна точка, которая минимизирует сумму самих расстояний — её называют геометрической медианой. Явной формулы для неё нет, поэтому её ищут итеративно.
Обозначение. Запись ‖xᵢ − Tₖ‖ — это просто расстояние между точкой-звездой xᵢ и текущим приближением Tₖ, вычисляемое по обычной формуле:
‖xᵢ − Tₖ‖ = √((xᵢ − xₜ)² + (yᵢ − yₜ)²)
Двойные чёрточки вместо одинарных — договорённость: одинарный модуль |·| занят для чисел на прямой, а для точек и векторов на плоскости берут ‖·‖.
Идея алгоритма
Начинаем с центроида. На каждом шаге каждая звезда «тянет» приближение к себе с силой, обратной расстоянию — то есть ближние звёзды влияют сильнее дальних. Формула обновления:
Tₖ₊₁ = ( Σ xᵢ / ‖xᵢ − Tₖ‖ ) / ( Σ 1 / ‖xᵢ − Tₖ‖ )
В числителе — координаты звёзд, взвешенные с весами wᵢ = 1 / ‖xᵢ − Tₖ‖. В знаменателе — сумма тех же весов (для нормировки). Чем ближе звезда — тем толще её «ниточка», тем сильнее она притягивает следующее приближение.
Демонстрация
Ниже — 8 звёзд. Зелёный крестик — центроид (стартовая точка). Золотая точка — текущее приближение Tₖ. Толщина линий показывает веса 1/‖xᵢ − Tₖ‖. Нажимайте «Шаг», чтобы посмотреть, как приближение сходится к геометрической медиане.
Итерация: 0 Сумма расстояний: — Сдвиг за шаг: —
Что стоит заметить
- На первом шаге сдвиг большой, дальше он стремительно уменьшается — это и есть «стабилизация», упомянутая в задаче.
- Сумма расстояний на каждом шаге только уменьшается (или остаётся такой же).
- Геометрическая медиана почти никогда не совпадает с центроидом — поэтому
B₂ ≠ 0.
- Если
Tₖ случайно попадёт ровно в одну из звёзд — в знаменателе возникнет ноль. В реальном коде в таких случаях добавляют крошечное ε.