Найти точку, сумма расстояний которой до множества других точек минимальна

Question

У меня есть один набор (X) точек (не очень большой, скажем, 1-20 баллов) и второй (Y), гораздо больший набор точек. Мне нужно выбрать некоторую точку из Y, сумма расстояний до всех точек из X минимальна.

Мне пришла в голову мысль, что я буду рассматривать X как вершины многоугольника и найду центроид этого многоугольника, а затем выберу точку из Y, ближайшую к центроиду. Но я не уверен, минимизирует ли центроид сумму своих расстояний до вершин многоугольника, поэтому я не уверен, что это хороший способ? Есть ли алгоритм для решения этой проблемы?

Точки определяются географическими координатами.

Answer 1

Центр тяжести многоугольника может быть неправильным, но такая точка существует.

В статье: n-эллипсы и проблема минимального расстояния показано, что если точки (называемые фокусами, ваш набор X) не коллинеарны, то

• Существует уникальная точка (называемая центром), для которой сумма расстояний минимизирована. Эта точка такова, что сумма единичных векторов от этой точки до фокусов равна нулю!

• Местоположением точек, для которых сумма расстояний постоянна, является выпуклая кривая (называемая n-эллипсом), содержащая центр

• n-эллипс для расстояния D полностью содержит n-эллипс для любого другого расстояния D ', для которого D'

Таким образом, вы можете использовать алгоритм подъема на холм, чтобы найти центр.

Конечно, эти n-эллипсы не обязательно являются кругами, поэтому выбор точки, ближайшей к центру, может не сработать, но может быть хорошим приближением.

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

Надеюсь, это поможет.

Answer 2

Поскольку вам нужна минимальная сумма расстояний, я считаю, что вы можете уменьшить набор точек X до его пространственного среднего значения. Затем вы можете использовать KDTree или какое-либо дерево пространственного разбиения, чтобы найти точку в Y, ближайшую к пространственному среднему X. Использование дерева пространственного разбиения может сэкономить немало работы по сравнению с проверкой всех возможных точек.

Answer 3

Если вы хотите минимизировать сумму квадратов расстояний (а не сумму расстояний), то точка, которая минимизирует эту сумму, является средним числом точек в X.

Доказательство:

sum(squares of distances) = (x-x0)^2 + (y-y0)^2 + (x-x1)^2 + (y-y1)^2 + ... 

d/dx sum(squares of distances) = 2(x-x0) + 2(x-x1) + ... = 2(Nx - x0 - x1 - ...)

сумма минимизируется, когда производная равна нулю, что происходит, когда Nx = x0+x1+..., поэтому x = (x0+x1+...)/N

Производная симметрична относительно этой точки, а функция квадратична, поэтому я уверен, что ближайшая точка Y к этой средней точке является лучшей.

Минимизация расстояний сложнее, но я подозреваю, что тот же алгоритм, с большей свободой в наборе Y, который вы тестируете, также будет работать.

Answer 4

Извините, что предложил грубую силу. То, как поставлен вопрос, мы не знаем, где лежат X, Y. Предположим, что X - 30 баллов, Y - 1000 баллов. Тогда для каждой точки Y сумма 30 расстояний. Всего 30000 расчетов, выполненных в один миг. Это гарантирует минимум. Найти некоторый «центр» X и выбрать ближайший Y будет только приблизительным решением.

Более интересный вопрос - найти такую ​​точку только для X. игнорировать Y. Только для X трех точек точка Ферма-Торичелли решает задачу.