| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > найближайшие две точки |
| Автор: Hohhi 8.6.2009, 17:32 |
| Необходимо написать программу, которая в заданном множестве точек на плоскости находит две точки расстояние между которыми максимально/минимально. Перебор элементарный. Хотелось бы сделать жадным методом? Возможно ли? или как-то более эффективно? |
| Автор: maxdiver 8.6.2009, 17:35 |
| Ну для двух ближайших точек простых быстрых алгоритмов точно нет. За N log N есть известный алгоритм "разделяй-и-властвуй", см., например, Кормена или Шамоса. Для двух наиболе удаленных точек я не знаю более простого алгоритма, чем строить выпуклую оболочку (опять же за N log N) и искать ответ в ней (это можно за N сделать). |
| Автор: Hohhi 8.6.2009, 17:38 |
| maxdiver, Ясно, с Корменом разберусь, спасибо |
| Автор: Hohhi 8.6.2009, 17:54 |
| подскажи только главу, а то торможу чего то, читал когда то динамического программирования, не помню подобную задачу |
| Автор: maxdiver 8.6.2009, 19:13 |
| Это совсем не динамическое программирование, эта глава прямо так и называется "Вычислительная геометрия" (в моей версии книги - под номером 33), в ней есть 33.4 "Поиск пары ближайших точек" и 33.3 "Построение выпуклой оболочки" - то, что тебе нужно. |
| Автор: Hohhi 8.6.2009, 19:33 |
| maxdiver, главы совпадают, спасибо |
| Автор: Pavia 8.6.2009, 20:58 | ||||
Есть. Через инверсную геометрию задача сводиться к поиску максимальных.
А вот выпуклую оболочку можно построить быстрее чем за N log N |
| Автор: maxdiver 8.6.2009, 21:59 | ||||
| Pavia Ну я сказал, _простых_ нет  Инверсная геометрия + нетривиальный алгоритм для выпуклой оболочки явно к таковым не относятся ))
Кстати, а что, разве после преобразования инверсии все расстояния станут обращениями себя же? Или почему тогда ближайшая пара станет == наиболее удаленной паре?
И выпуклую оболочку быстрее - разве что за O (N log H) алгоритмом Чана? Если H близко к N, то толку-то (особенно учитывая, что она под логарифмом). |
