Пересение прямоугольников

From

Eldar Ulukhanov (2:5020/1057.226)

To

All ()

Date

2003-03-20T19:54Z

Area

RU.ALGORITHMS

Hello, All!

Есть множество прямоугольков на плоскости и надо найти всевозможные попарные
пересечения этих прямоугольников.
Эту задачу можно решить перебрав двойным циклом все возможные пары
прямоугольников. Однако при большом количестве прямогульников на это тратиться
много времени.

Не подскажет ли Олл алгоритм нахождения пересечений со сложность меньше, чем
O(n2)

Есть идея, что сложность можно уменьшить за счет предварительного
упорядочивания множества и поиском его пересечения со всеми прямоугольниками.
Однако не понятно как эти прямугольники упорядочивать и как искать пересечение
этого упорядоченного множества с одним элементом меньше чем O(n).

За ранее благодарен за любые советы.

Всего хорошего, All!
                                                    Eldar Ulukhanov
--- C++ - это не язык. Это мировоззрение, меняющее образ мышления.
 * Origin: CD и DOOMай (2:5020/1057.226)