222
правки
Изменения
Нет описания правки
Данный алгоритм работает за <tex> O(n \log n) </tex> и за линейное количество памяти и идеально подходит для нахождения какого-нибудь пути между конечными вершинами. Но иногда нужно найти кратчайший путь, и этот алгоритм не подходит, хоть и дает хорошее приближение.
На сегодняшний день, точные решения в лучшем случае работают за <tex> O(n^2) </tex> времени и памяти (здесь и далее <tex> n </tex> {{---}} количество всех вершин).
Теперь рассмотрим точное решение с помощью построения графа видимости. После его построения, как и в случае с трапецоидной картой, путь ищется стандартными алгоритмами.
{{Определение
|definition =
}}
{{Определение
|definition =
'''visibility graph''' {{---}} граф, вершины которого {{---}} вершины полигонов. Между вершинами <tex> u </tex> и <tex> v </tex> существует ребро, если из <tex> u </tex> видна <tex> v </tex>.
}}
В худшем случае в таком графе может быть <tex> O(n^2) </tex> ребер. Однако по некоторым ребрам кратчайший путь точно не пройдет, и такие ребра из графа можно удалить.
{{Лемма
}}
По доказанным леммам любое ребро кратчайшего пути содержится в графе, таким образом для нахождения кратчайшего пути осталось найти кратчайший путь в этом графе от <tex> S </tex> до <tex> T </tex>. Рассмотрим алгоритмы построения графа видимости.
=== Построение visibility графа ===
