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

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

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

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

10
задан Pawel Markowski 5 January 2011 в 22:27
поделиться