Изменения
→Visibility graph
Пусть кратчайший путь {{---}} не ломаная. Тогда рассмотрим участок пути, где он не является прямым. По неравенству треугольника в окрестности этого участка мы сможем немного срезать. Значит этот путь не кратчайший. Противоречие, значит лемма доказана.
}}
Таким образом для нахождения точного решения определим 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 графа, так что мы нашли то, что нужно.
Чтобы уменьшить объем графа, из него можно удалить ребра, по которым точно не пройдет путь.
|proof=
[[Файл:edgeToDelete.jpg|150px|thumb|right|Удаляем <tex> BD </tex>]]
Путь проходящий через ребро <tex> BD </tex> будет длинеедлиннее, чем через соседей точки <tex> B </tex>, так как по неравенству треугольника <tex> AB + BD < AD </tex>
}}
