Геометричний пошук, Детальна інформація

5. Обійдемо дерево Tk зліва направо, заносячи ребра до списку lk.

6. if k \xF0A3\xF020n then k \xF0AC\xF020k + 1 and goto 4;

Крок 1 алгоритму передобробки вимагає O(N * log N) часу. Оскільки кожна смуга містить O(N) відрізків, то розмір всіх дерев Tk , k = 1, ..., n + 1, дорівнює O(N), а глибина – O(log N). Тому час вставки та видалення ребра дорівнює O(log N). Кожне ребро графу G лише один раз додається та один раз видаляється зі структури даних. Якщо граф G представлено реберним списком з подвійними зв’язками, то пошук вхідних та вихідних ребер для вершини vk-1 на 4-му кроці вимагатиме константний час. Оскільки граф G має O(N) ребер, то на виконання усіх 4-их кроків алгоритму витратиться O(N * log N) часу. Виконання 5 кроку відбувається за час O(N), оскільки список lk може містити O(N) ребер. Оскільки утворюється N дерев Tk, то на виконання усіх 5-их кроків алгоритму необхідно витратити O(N2) часу.

Теорема. Задачу локалізації точки методом смуг можна виконати за час O(log N) з часом передобробки O(N2) та витратами пам’яті O(N2).

Метод ланцюгів.

Означення. Ланцюгом C = {u1, u2, ..., up} називається планарний граф з вершинами {u1, u2, ..., up} та ребрами {(ui, ui+1) : i = 1, ..., p -1} .

Означення. Ланцюг C = {u1, u2, ..., up} називається монотонним по відношенню до прямої l, якщо довільна пряма, ортогональна l, перетинає C лише в одній точці.

-

F

H

N

b

0

N

-



H

ue

*

3перевірка визначить по яку сторону від ребра uiui+1 лежить точка z.

Теорема. Локалізація довільної точки відносно p вершинного ланцюга реалізується за час O(log p).

Припустимо, що існує множина E = {C1, C2, ..., Cr} ланцюгів, монотонних відносно l однієї прямої та які мають наступні властивості:

1. Об’єднання усіх елементів E містить заданий планарний граф.

2. Для довільної пари ланцюгів Ci та Cj з E ті вузли Ci, які не є вузлами Cj, лежать по одну сторону від Cj.

Така множина називається повною множиною монотонних ланцюгів графа G. З другої властивості випливає, що ланцюги з E впорядковані.

Теорема. Дано r ланцюгів і в найдовшому ланцюгу p вершин. Локалізація точки розв’язується за час O(log r * log p).

Означення. Нехай G – планарний граф з множиною вершин v1, ..., vN, де вершини проіндексовані так, що i < j тоді і тільки тоді, коли y(vi) < y(vj) або y(vi) = y(vj) і x(vi) > x(vj). Вершина vj називається регулярною, якщо існують такі цілі i < j < k, що (vi, vj) та (vj, vk) – ребра G. Граф G є регулярним, якщо кожна його вершина vj регулярна при 1 < j < N (за виключенням двох крайніх вершин v1 та vN).

Позначимо через IN(vj) та OUT(vj) множини ребер, які входять та виходять з вершини vj. Нехай ребра в IN(vj) впорядковані за кутом проти годинникової стрілки, а ребра в OUT(vj) – за годинниковою стрілкою. За припущенням про регулярність графа ці множини не порожні для кожної некрайньої вершини.

Теорема. Для довільної vj можна побудувати y - монотонний ланцюг від v1 до vj.

Доведення. Твердження справедливе для j = 2. Припустимо, що твердження справедливе для всіх k < j. Оскільки vj регулярна, то існує таке i < j, що (vi, vj) – ребро G. Але за припущенням індукції існує ланцюг C від v1 до vi, монотонний відносно осі y. Тоді його з’єднання з ребром (vi, vj) дасть також монотонний ланцюг.