113
правок
Изменения
Нет описания правки
|proof=Копирование двух РСДС в один занимает <tex>O(n)</tex> времени, заметающая прямая работает <tex>O(n \log{n} + k \log{n})</tex> времени по лемме. Создание граней работает линейное время от сложности <tex>O(S_1, S_2)</tex>. Маркировка граней РСДС работает за <tex>O(n \log{n} + k \log{n})</tex>.
}}
== См.также ==
*[[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых]]
*[[Пересечение множества отрезков]]
== Источники ==
* de Berg, Cheong, van Kreveld, Overmars. Computational Geometry, Algorithms and Applicants, 2008. pp. 33-39
[[Категория: Вычислительная геометрия]]
[[Категория: ППЛГ и РСДС]]
