222
правки
Изменения
м
Нет описания правки
== Visibility graph ==
{|align="right"|-valign="top"|[[Файл:trap.png|200px|thumb|right|Путь с препятствиями через трапецоидную карту]]|[[Файл:notShort.png|300px|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|В таком случае мы всегда сможем срезатьShort cut]]
Пусть путь проходит(в смысле вершины) через какую-то другую точку. Рассмотрим окрестность этой точки. По неравенству треугольника мы сможем немножко срезать. Значит этот путь не кратчайший. Противоречие, значит лемма доказана.
}}
