|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Eldar Ulukhanov 2:5020/1057.226 20 Mar 2003 20:54:00
To : All
Subject : Пересение прямоугольников
--------------------------------------------------------------------------------
Есть множество прямоугольков на плоскости и надо найти всевозможные попарные
пересечения этих прямоугольников.
Эту задачу можно решить перебрав двойным циклом все возможные пары
прямоугольников. Однако при большом количестве прямогульников на это тратиться
много времени.
Hе подскажет ли Олл алгоритм нахождения пересечений со сложность меньше, чем
O(n2)
Есть идея, что сложность можно уменьшить за счет предварительного
упорядочивания множества и поиском его пересечения со всеми прямоугольниками.
Однако не понятно как эти прямугольники упорядочивать и как искать пересечение
этого упорядоченного множества с одним элементом меньше чем O(n).
За ранее благодарен за любые советы.
Всего хорошего, All!
Eldar Ulukhanov
--- C++ - это не язык. Это мировоззрение, меняющее образ мышления.
* Origin: CD и DOOMай (2:5020/1057.226)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
