222
правки
Изменения
м
→Visibility graph
Любой кратчайший путь от <tex> S </tex> до <tex> T </tex> с полигональными препятствиями представляет собой ломаную, вершины которой {{---}} вершины полигонов.
|proof=
Пусть путь проходит (в смысле вершины) через какую-то другую точку. Рассмотрим окрестность этой точки. По неравенству треугольника мы сможем немножко, да срезать. Значит этот путь не кратчайший. Противоречие, значит лемма доказано и все офигенно.
}}
