точки на плоскости..

даны n - точек на плоскости, надо найти какую-нибудь точку чтобы суммарное расстояние от неё до n точек было минимальным
в принципе задачу можно упростить до n = 3 или n = 4, но желательно что бы для любого n.
Не подскажите формулу, алгоритм?

 

al_4
Хм, это не центр масс системы из N материальных точек случаем?

 

хм.. честно хз)

щас определение глянул, вроде нет, не оно)
хотя щас посмотрю внимательной, может чего полезного найду)

 

... до n-1 точек было минимальным?

 

Используй алгоритмы минимизации выпуклых функций. Точного выражения этой точки для n>4 вроде как нет.

 

al_4
Для треугольника - это точка Торричелли:
http://www.problems.ru/thes.php?letter=18

 

Кстати да, очень интересная задача. Мне известен только численный метод.
Кстати, на algolist.ru утверждается, что ответом будет центр масс, что очевидно неверно.
Например, для точек на прямой: x=0, x=2, x=10. Ответ x0=2 (средняя точка после сортировки), а центр масс даст x0=4.

 

>Для треугольника - это точка Торричелли:

спасибо) кстати, три точки могут быть и на одной прямой. )

>до n-1 точек было минимальным?

эм.. слегка не понял вопрос)

>алгоритмы минимизации выпуклых функций
спс) гляну)

>на algolist.ru утверждается,
уу) забыл про него совсем, щас там поглядим.)
>Мне известен только численный метод.
Если не затруднит, то расскажите поподробней пожалуйста)


всем спасибо, куда "копать" понял)

 

al_4

думал надо искать не новую точку, а точку из n данных.

 

см. http://en.wikipedia.org/wiki/Geometric_median

 

RElf
Спасибо, самому что-то не удалось найти эту страницу )
Жаль только, что подтвердилось, что кроме последовательных приближений алгоритма не найдено, и большой вопрос, существует ли он...