Необходимо написать программу, которая в заданном множестве точек на плоскости находит две точки расстояние между которыми максимально/минимально.

Перебор элементарный. Хотелось бы сделать жадным методом? Возможно ли? или как-то более эффективно?

Ну для двух ближайших точек простых быстрых алгоритмов точно нет. За N log N есть известный алгоритм "разделяй-и-властвуй", см., например, Кормена или Шамоса.

Для двух наиболе удаленных точек я не знаю более простого алгоритма, чем строить выпуклую оболочку (опять же за N log N) и искать ответ в ней (это можно за N сделать).

maxdiver, Ясно, с Корменом разберусь, спасибо

подскажи только главу, а то торможу чего то, читал когда то динамического программирования, не помню подобную задачу

Это совсем не динамическое программирование, эта глава прямо так и называется "Вычислительная геометрия" (в моей версии книги - под номером 33), в ней есть 33.4 "Поиск пары ближайших точек" и 33.3 "Построение выпуклой оболочки" - то, что тебе нужно.

maxdiver, главы совпадают, спасибо

Есть. Через инверсную геометрию  задача сводиться к поиску максимальных.


 А вот выпуклую оболочку можно построить быстрее чем за  N log N

Это сообщение отредактировал(а) Pavia - 8.6.2009, 21:21

Pavia
Ну я сказал, _простых_ нет  Инверсная геометрия + нетривиальный алгоритм для выпуклой оболочки явно к таковым не относятся ))


Кстати, а что, разве после преобразования инверсии все расстояния станут обращениями себя же? Или почему тогда ближайшая пара станет == наиболее удаленной паре?


И выпуклую оболочку быстрее - разве что за O (N log H) алгоритмом Чана? Если H близко к N, то толку-то (особенно учитывая, что она под логарифмом).