Изменения

Пусть кратчайший путь проходит(в смысле вершины) через какую{{---то другую точку}} не ломаная. Рассмотрим окрестность этой точкиТогда рассмотрим участок пути, где он не является прямым. По неравенству треугольника в окрестности этого участка мы сможем немножко немного срезать. Значит этот путь не кратчайший. Противоречие, значит лемма доказана.

Таким образом создадим определим 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 графа, так что мы нашли то, что нужно.