222
правки
Изменения
м
Нет описания правки
== Visibility graph ==
[[Файл:trap.png|200px|thumb|rightleft|Путь с препятствиями через трапецоидную карту]][[Файл:notShort.png|200px|thumb|right|Такой путь не самый короткий]]
В общем, когда мы ищем путь от точки <tex> S </tex> до <tex> T </tex> с препятствиями(надо уточнить, что двигаем мы точку, а не какой-то полигон), можно построить [[Трапецоидная карта | трапецоидную карту]], соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе [[Алгоритм Дейкстры | Дейкстрой]] найти путь от <tex> S </tex> до <tex> T </tex>. Но этот путь не будет кратчайшим(кэп).
{{Лемма
Любой кратчайший путь от <tex> S </tex> до <tex> T </tex> с полигональными препятствиями представляет собой ломаную, вершины которой {{---}} вершины полигонов.
|proof=
[[Файл:short.png|150px|thumb|right|Ну в общем тут все очевидно]]
Пусть путь проходит(в смысле вершины) через какую-то другую точку. Рассмотрим окрестность этой точки. По неравенству треугольника мы сможем немножко, да срезать. Значит этот путь не кратчайший. Противоречие, значит лемма доказано и все офигенно.
}}
