Изменения

Говорят, что вершина <tex> u </tex> <i> ''видна </i>'' (англ. mutually visible) из <tex> v </tex>, если отрезок <tex> uv </tex> не пересекает ни одного препятствия.

''Граф видимости'' (англ. visibility graph''' ) {{---}} граф, вершины которого {{---}} вершины полигонов. Между вершинами <tex> u </tex> и <tex> v </tex> существует ребро, если из <tex> u </tex> видна <tex> v </tex>.

По доказанным леммам любое ребро кратчайшего пути содержится в графе. Таким образом, таким образом для нахождения кратчайшего пути осталось найти кратчайший путь в этом графе от <tex> S </tex> начальной до <tex> T </tex>конечной вершины.

Если делать наивно, то есть для Для каждой пары вершин проверять проверяем, можно ли добавить ли такое ребро(между ними, то есть нет ли пересечений с полигонами. <tex> O(n^2)</tex> пар вершин и <tex> O(n) </tex> ребер, будет то есть <tex> O(n^3) </tex>.

Однако можно это сделать за <tex> O(n ^ 2 \log n) </tex>. Идея алгоритма проста : для каждой вершины найдем видимые из нее вершины независимо. Если научиться делать это за <tex> O(n \log n) </tex>, задача решена, так как всего точек <tex> n </tex>. Будем рассматривать точки слева направо, таким образом потребуется рассматривать только правую половину плоскости, так как ребра, которые должны идти в левую будут уже добавлены ранее.