27. Локализация точки на планарном подразбиении. Алгоритмы. Оценки.

Перечислить объекты, принадлежащие области(задача локализации точки).

Пусть есть множество областей(планарный граф, то есть граф на плоскости, ребра которого пересекаются только в вершинах) и объект(точка). Необходимо определить какой области принадлежит объект.

1) Задача решается за O(n).

Принадлежность точки конкретной области определяется с помощью луча, проведенного из точки. Если количество пересечений с ребрами области нечетное, то точка принадлежит этой области.

Планарный граф задается вершинно-реберным списком: для каждого ребра известны начало N0, конец N1, номер ближайшего ребра при повороте вокруг начала по часовой стрелке E0, то же против часовой стрелки E1, номер смежной области слева F0, номер смежной области справа F1. Для каждой вершины указано одно из инцидентных ребер.

2) Существует способ решить задачу быстрее.

Разделяем все пространство на полосы (горизонтальные линии проходят через вершины графа) и упорядочим их по координате у. Определяем принадлежность точки одной из полос (сравнение координат у). Затем найдем и упорядочим (по координате Х на средней линии полосы) отрезки, образованные ребрами графа при пересечении с границами полос – получим упорядоченный список k отрезков(k = 3) – a b c. Кроме того построим упорядоченный список k+1 областей для каждой полосы (слева направо) – 1 2 3 1. Таким образом определив ближайший слева от точки отрезок m (отрезок a, m=1) с помощью векторного произведения вектора отрезка и вектора из начала отрезка в точку, вычисляем, что точка принадлежит области, стоящей в списке под номером m+1 (область 2).

Время предобработки О(n^2logn): упорядочивание полос О(nlogn), упорядочивание отрезков О(nlogn), упорядочивание областей – не зависит от n (берем отрезок и смотрим какая область лежит слева от него).

Время обработки запроса при неизменном графе - О(logn).

3) Плоское заметание.

Есть горизонтальная прямая, которая движется в направлении сверху – вниз. Статус прямой - количество ребер, которые пересекает данная прямая, упорядоченных по координате Х. Статус прямой изменяется в некоторых точках – событиях, число которых конечно. Необходимо определить правила изменения статуса.

Рассмотрим множество областей(планарный граф) и точку. Определить в какую область попала точка.

К крайней левой точке добавляем горизонтальный луч влево, к крайней правой точке добавляем горизонтальный луч вправо. Разбиваем граф на последовательность цепей из левого луча в правый. Количество таких цепей O(n^2).

Упорядочим цепи, то есть отсортируем их по возрастанию. Каждая точка верхней цепи должна лежать не ниже соответствующей(по координате Х) точки нижней цепи. Формально задача упорядочивания цепей решается так: 1)найдем вершину, где две цепи расходятся; 2) найдем знак вектора - результата векторного произведения двух векторов ребер графа.

Разобьем граф на вертикальные полосы, проходящие через вершины графа, за время О(logn).

Определим между какими двумя цепями в пределах нужной полосы лежит точка за О(logn).

Отрезок ребра графа, соответствующий этой полосе и принадлежащий верхней цепи из найденной пары, будет определять искомую область. То есть искомой областью будет являться правая смежная этому ребру область.

Время обработки запроса при неизменном графе - О(logn).