139
правок
Изменения
→Наивный алгоритм. O(n ^ 3)
=== Построение visibility графа ===
==== Наивный алгоритм. <tex> O(n ^ 3) </tex> ====
Если делать <s> в тупую</s> наивно, т. е. для каждой пары вершин проверять можно ли добавить ли такое ребро(нет ли пересечений с полигонами), будет <tex> O(n^3) </tex> (зато просто пилится, даже не надо объяснять как).
[[Файл:search.png|400px|thumb|right|Дерево поиска пересекаемых ребер]]
==== Lee’s Algorithm. <tex> O(n ^ 2 \log n) </tex> ====
[[Файл:zam.png|400px|thumb|left|Заметание плоскости вращающимся лучом]]
