222
правки
Изменения
м
→Lee’s Algorithm. O(n ^ 2 \log n)
[[Файл:search.png|400px|thumb|right|Дерево поиска пересекаемых ребер]]
==== Lee’s Algorithm. <tex> O(n ^ 2 \log n) </tex> ====
Однако можно это сделать за <tex> O(n ^ 2 \log n) </tex>. Пусть мы хотим Для каждой вершины найдём все видимые из неё вершины <tex> v </tex> найти при помощи метода плоского заметания. Нам нужно решить следующую задачу: на плоскости дано множество отрезков (рёбер препятствий) и точка p. Найти все концы отрезков, видимые из нее точки p. Будем заметать плоскость вращающимся лучом с началом в точке p. Статусом заметающей прямой будет отрезки, которые её пересекают, упорядоченные по возрастанию расстояния от точки p до точки пересечения. Точками событий будут концы отрезков. Итак, первым делом вершины w ∈ W сортируются по углу между лучом vw и вертикальной полуосью, проходящей через v. Такая сортировка выполняется за O(nlog(n)), например, сортировкой слияниями. Затем происходит инициализация множества видимых вершин (по умолчанию, такое множество пустое). Далее начинается заметание плоскости. В порядке сортировки вершин для каждой из них выполняется проверка: видна ли вершина w из вершиныv. Теперь мы будем перебирать ребра не Поскольку такая проверка означает наличие пересечений, которые хранятся в случайном порядкесбалансированном дереве, а так чтобы можно было проверять она может быть выполнена за логарифмO(log(n)). Если вершина видима, необходимо добавить её в список видимых вершин. И, наконец, вне зависимости от видимости вершины, необходимо изменить статус заметающей прямой. Для этого посортим , для текущей вершины w необходимо удалить из списка текущих пересечений все рёбра (отрезки), которые заканчиваются в этой вершине (лежат слева от прямой vw) и добавить все вершины по полярному углу рёбра (только теотрезки), которые в ней начинаются (лежат справа нашей, ибо очевидно, что назад можно уже не смотретьот прямой vw) и запилим сбалансированное двоичное дерево поиска.
Вершин у нас <tex> O(n) </tex>, сортим за <tex> O(n \log n) </tex> плюс запросы в дереве за <tex> O(n) * O(\log n) </tex>. Итого что хотели.
