Изменения

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

Visibility graph и motion planning

22 байта добавлено, 16:54, 15 февраля 2015
м
Псевдокод
answer.add(<tex>w</tex>)
'''for''' Segment <tex>s</tex> ending in <tex>w</tex>
status.delete(<tex>s</tex>)
'''for''' Segment <tex>s</tex> beginning in <tex>w</tex>
status.add(<tex>s</tex>)
'''return''' answer
В качестве статуса нужно использовать структуру данных, позволяющую добавлять и удалять из нее отрезки за <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>).
222
правки

Навигация