222
правки
Изменения
м
→Visibility graph
Рассмотрим задачу нахождения кратчайшего пути от точки <tex> S </tex> до <tex> T </tex> с препятствиями. Для начала рассмотрим движение материальной точки, случай произвольного полигона будет [[Visibility graph и motion planning#Motion planning|позднее]]. Для нахождения можно построить [[Трапецоидная карта | трапецоидную карту]], соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе любым алгоритмом поиска кратчайших путей (например, алгоритмом [[Алгоритм Дейкстры|Дейкстры]] или [[Алгоритм A*|A*]]) найти путь от <tex> S </tex> до <tex> T </tex>. Но этот путь, очевидно, не будет кратчайшим.
Однако этот алгоритм обширно используется, так как трапецоидная карта дает хорошее приближение, строится за <tex> O(n \log n) </tex> и занимает <tex> O(n) </tex> памяти, в то время как точные решения в лучшем случае работают за <tex> O(n^2) </tex> и требуют <tex> O(n^2) </tex> памяти(здесь и далее <tex> n </tex> {{---}} количество всех вершин).
{{Лемма
