222
правки
Изменения
м
→Overmars and Welzl’s Algorithm O(n ^ 2)
==== Overmars and Welzl’s Algorithm <tex> O(n ^ 2) </tex> ====
[http://igitur-archive.library.uu.nl/math/2006-1214-201604/overmars_88_new_methods.pdf visibility graph при помощи rotation tree]
Ковалев сказал что это можно рассказывать по желанию.
Каким-то магическим образом, можно избавиться и от логарифма в асимптотике. Это делается с помощью [http://bit.ly/1eEqTzk rotation tree]. Про него рассказывал Антон Ков., но как-то мутно и не очень понятно. Суть такова, что мы обходим вершины в таком хитром порядке, что почти не просматриваем лишнее и получаем асимптотику {{---}} квадрат.
/*мне лень это переводить, и так понятно/непонятно*/
== Motion planning ==
[[Файл:mink.png|200px|thumb|left|Раздуваем препятствия]]
