Пересечение простых многоугольник (выч. геометрия)

[giantwe]

Столкнулся с одной интересной задачей.

Найти пересечение 2 простых (т.е. без самопересечений) многоугольников за линейное время - $O(n+k)$, где n - суммарное количество вершин, k - количество пересечений. Результат работы алгоритма - пары пересекающихся сторон многоугольников.

Казалось бы очень простая формулировка, но в интернете много на данную тему не найти. За $O(nlog(n) + k)$ - пожалуйста. Единственное что удалось откопать так это упоминание, что задача за указанное время решаема со ссылкой на U. Finke and K. Hinrichs: Overlaying simply connected planar subdivisions in linear time. Но в свободном доступе её нет, да и не уверен я, что это именно то что нужно.

Кто-то сталкивался с такой задачей?

[Sonic86]

Я Вам точно не скажу, но попробуйте скачать книгу Ласло Вычислительная геометрия и компьютерная графика на С++. Там что-от подобное точно есть.