Ответ 1
Это называется "Центр расстояния" и отличается от центра тяжести.
Во-первых, вы должны определить, какую меру расстояния вы используете. Если предположить, что вы используете стандартную метрику d = sqrt ((x1-x2) ^ 2 + (y1-y2) ^ 2), то она не является единственной, и задача минимизирует эту сумму.
Самый простой пример, чтобы показать этот ответ, не является уникальным примером прямой линии. Любая точка между двумя точками имеет равное полное расстояние от всех точек.
В 1D правильным ответом будет любой ответ, который имеет одинаковое количество точек справа и слева. Пока это верно, тогда любое перемещение влево и вправо будет увеличиваться и уменьшать левую и правую стороны на одну и ту же величину и, таким образом, оставлять расстояние одинаковым. Это также доказывает, что центроид не обязательно правильный ответ.
Если мы переходим к 2D, это уже не так, поскольку sqrt делает проблему взвешенной. Удивительно, но, похоже, не стандартный алгоритм! На странице здесь используется метод грубой силы. Я этого никогда не знал!
Если бы я хотел использовать алгоритм, я бы нашел медианную точку в X и Y в качестве начальной точки, а затем использовал алгоритм спуска градиента - это получило бы ответ довольно быстро. Все уравнение заканчивается квадратичным, поэтому кажется, что должно быть точное решение.