геометрия - Кратчайшее растояние до вершин многоугольника

Я раньше не видела этой задачи, но меня заинтересовала рекуррентная формула, приведенная Вами. Я разобралась, откуда она взялась, но пока не вижу, будет ли процесс сходиться. На примере (выпуклый 10-угольник) сходится весьма быстро и, видимо, именно туда, куда надо.

Запишем искомую величину в координатах, $%S(x,y)=\sum \sqrt{(x-x_i)^2+(y-y_i)^2}$%. Производная по x равна $%S_x'=\sum \frac{x-x_i}{\sqrt{(x-x_i)^2+(y-y_i)^2}}$%. Приравняем ее к 0. Равенство можно переписать в виде $$\sum \frac{x}{\sqrt{(x-x_i)^2+(y-y_i)^2}}=\sum \frac{x_i}{\sqrt{(x-x_i)^2+(y-y_i)^2}}$$.
Вынося в левой части x, получаем равенство $$x=\frac{\sum \frac{x_i}{\sqrt{(x-x_i)^2+(y-y_i)^2}}}{\sum \frac{1}{\sqrt{(x-x_i)^2+(y-y_i)^2}}}.$$ Такое же равенство можно построить для y. Объединяя их в пару (x,y) получим векторную запись равенства (которая и приведена автором метода).

Идея рекуррентного соотношения: в правую часть подставляем k-ое приближение, в левой получаем (k+1)-ое. Я запрограммировала этот процесс для одного 10-угольника и 2 начальных точек, процесс сходится достаточно быстро:

Красная последовательность началась с точки (0,0), а зеленая - с точки (10, 12)

Вариант расчета для случайных точек. Синим показан центр тяжести (среднее арифметическое вершин).

Если каждой вершине присвоены коэффициенты $%k_i$%, так что минимизируется взвешенная сумма расстояний, то исследуемая функция принимает вид $%S(x,y)=\sum k_i\sqrt{(x-x_i)^2+(y-y_i)^2}$%.
Производная по x равна $%S_x'=\sum k_i\frac{x-x_i}{\sqrt{(x-x_i)^2+(y-y_i)^2}}$%. Равенство производной нулю можно переписать в виде $$\sum k_i\frac{x}{\sqrt{(x-x_i)^2+(y-y_i)^2}}=\sum k_i\frac{x_i}{\sqrt{(x-x_i)^2+(y-y_i)^2}}$$.
Вынося в левой части x, получаем равенство $$x=\frac{\sum \frac{k_i x_i}{\sqrt{(x-x_i)^2+(y-y_i)^2}}}{\sum \frac{k_i}{\sqrt{(x-x_i)^2+(y-y_i)^2}}}.$$

Из этого равенства можно сделать рекуррентное соотношение.

К вопросу о точке наименьшего расстояния.