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

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

Z

u

(

F

@

o

"

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) дасть також монотонний ланцюг.

Теорема. Довільний регулярний граф можна розбити на повну множину ланцюгів, монотонних відносно осі y.

Доведення. Покажемо виконання двох властивостей повної множини монотонних ланцюгів. Позначимо через W(e) вагу ребра e – кількість ланцюгів, яким належить e. Введемо позначення: