Visibility graph и motion planning

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!


Visibility graph

В общем, когда мы ищем путь от точки [math] S [/math] до [math] T [/math] с препятствиями, можно построить трапецоидную карту, соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе Дейкстрой найти путь от [math] S [/math] до [math] T [/math]. Но этот путь не будет кратчайшим(кэп).

Лемма:
Любой кратчайший путь от [math] S [/math] до [math] T [/math] с полигональными препятствиями представляет собой ломаную, вершины которой — вершины полигонов.
Доказательство:
[math]\triangleright[/math]
Пусть путь проходит через какую-то другую точку. Рассмотрим окрестность этой точки. По неравенству треугольника мы сможем немножко, да срезать. Значит этот путь не кратчайший. Противоречие, значит лемма доказано и все офигенно.
[math]\triangleleft[/math]

Motion planning

Здесь могла быть Ваша реклама. Но скоро будет конспект.

Источники

  • Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (2008), Computational Geometry: Algorithms and Applications (3rd edition), Springer-Verlag, ISBN 978-3-540-77973-5 Chapter 15 page 324-331