Изменения

[[Файл:search.png|400px|thumb|right|Дерево поиска пересекаемых ребер]]

==== Lee’s Algorithm. <tex> O(n ^ 2 \log n) </tex> ====

Однако можно это сделать за <tex> O(n ^ 2 \log n) </tex>. Для каждой вершины найдём все видимые из неё вершины при помощи метода плоского заметания. Нам нужно решить следующую задачу: на плоскости дано множество отрезков (рёбер препятствий) и точка p. Найти все концы отрезков, видимые из точки p. Будем заметать плоскость вращающимся лучом с началом в точке p. Статусом заметающей прямой будет отрезки, которые её пересекают, упорядоченные по возрастанию расстояния от точки p до точки пересечения. Точками событий будут концы отрезков. Итак, первым делом вершины w ∈ W сортируются по углу между лучом vw и вертикальной полуосью, проходящей через v. Затем происходит инициализация множества видимых вершин (по умолчанию, такое множество пустое). Далее начинается заметание плоскости. В порядке сортировки вершин для каждой из них выполняется проверка: видна ли вершина 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>. Итого что хотели.

==== Overmars and Welzl’s Algorithm <tex> O(n ^ 2) </tex> ====