139
правок
Изменения
→Visibility graph
Пусть путь проходит(в смысле вершины) через какую-то другую точку. Рассмотрим окрестность этой точки. По неравенству треугольника мы сможем немножко, да срезать. Значит этот путь не кратчайший. Противоречие, значит лемма доказана и все офигенно.
}}
Так же, что бы уменьшить объем финального графа, следует удалить из него ребра, по которым точно не пройдет путь.{{Лемма|statement=Если у ребра на предыдущю точку от данной левый поворот, а на следующую, от данной, правый - то ребро, идущее к текущей точке может быть удалено.|proof=[[Файл:edgeToDelete.jpg|150px|thumb|right|Удаляем <tex>BD</tex>]]Очевидно, что путь проходящий через ребро <tex>BD</tex> будет длинее, чем через соседей точки <tex>B</tex>. Тк по неравенству треугольника <tex>AB + BD</tex> < <tex>AD</tex>}}По этой лемме запилим этому сосздадим visibility graph. Его вершины {{---}} вершины полигонов. Между вершинами <tex> u </tex> и <tex> v </tex> существует ребро, если из <tex> u </tex> <i> видна </i>(mutually visible) <tex> v </tex> (ребра полигонов тоже входят в этот граф). Теперь, если мы добавим к множеству вершин <tex> S </tex> и <tex> T </tex> (и ребра в видимые вершины), у нас получится граф, в котором опять же Дейкстрой находим кратчайший путь. По лемме любое ребро кратчайшего пути {{---}} ребро visibility графа, так что мы нашли то, что нужно.
=== Построение visibility графа ===
