222
правки
Изменения
м
Нет описания правки
=== Построение 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> ====
Однако можно это сделать за <tex> O(n ^ 2 \log n) </tex>. Пусть мы хотим из вершины <tex> v </tex> найти все видимые из нее вершины. Теперь мы будем перебирать ребра не в случайном порядке, а так чтобы можно было проверять за логарифм.
Вершин у нас <tex> O(n) </tex>, сортим за <tex> O(n \log n) </tex> плюс запросы в дереве за <tex> O(n) * O(\log n) </tex>. Итого что хотели.
==== Overmars and Welzl’s Algorithm <tex> O(n ^ 2) </tex> ====
Каким-то магическим образом, можно избавиться и от логарифма в асимптотике. Это делается с помощью [http://bit.ly/1eEqTzk rotation tree]. Про него рассказывал Антон Ков., но как-то мутно и не очень понятно. Суть такова, что мы обходим вершины в таком хитром порядке, что почти не просматриваем лишнее и получаем асимптотику {{---}} квадрат.
