Изменения

Перейти к: навигация, поиск

Visibility graph и motion planning

138 байт добавлено, 23:10, 10 февраля 2015
м
подписи к картинкам
В качестве статуса нужно использовать структуру данных, позволяющую добавлять и удалять из нее отрезки за <tex> O(\log n) </tex> и извлекать минимум за <tex> O(1) </tex> или <tex> O(\log n) </tex>. В этом случае достигается асимптотика <tex> O(n^2 \log n) </tex>, так как для каждой из <tex> n </tex> точек выполняется сортировка(<tex> O(n \log n) </tex>), обновление статуса (суммарно <tex> O(n \log n) </tex>, так как каждый отрезок добавляется и удаляется из статуса только один раз) и запросы ближайшего отрезка (<tex> O(\log n) </tex> или <tex> O(1) </tex> на точку, то есть <tex> O(n \log n) </tex> или <tex> O(n) </tex>).
|
[[Файл:Zamrefr1.png|250px|thumb|right|Обновление статуса заметающего луча: добавляем ребра <tex> w_1 w_5 </tex> и <tex> w_1 w_2 </tex> в статус]][[Файл:Zamrefr2.png|250px|thumb|right|Обновление статуса заметающего лучаДобавляем ребра <tex> w_3 w_2 </tex> и <tex> w_3 w_4 </tex> в статус]][[Файл:Zamrefr3.png|250px|thumb|right|Обновление Удаляем ребра <tex> w_3 w_2 </tex> и <tex> w_1 w_2 </tex> из статуса заметающего луча]]
|}
222
правки

Навигация