Минимаксная "сортировка"

From

Valentin Davydov ()

To

All

Date

2003-01-09T17:37:41Z

Area

RU.ALGORITHMS

From: Valentin Davydov <val@sqdp.trc-net.co.jp>

Есть множество из N точек в метрическом пространстве, надо отсортировать
их следующим образом: в качестве первой точки берётся некая произвольная, 
а каждая следующая выбирается так, чтобы минимальное расстояние от неё до 
уже выбранных было бы самым большим среди всех оставшихся точек. Все точки 
сортировать необязательно, достаточно первых K, причём K обычно много 
меньше, чем N. Тривиальный алгоритм прямого перебора линеен по N и 
квадратичен по K. Можно ли его как-нибудь ускорить?

Вал. Дав.
--- ifmail v.2.15dev5
 * Origin: St. Petersburg State University (2:5020/400)