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

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 лише в одній точці.

Проекцію l(z) заданої точки z на l можна локалізувати методом двійкового пошуку в єдиному з інтервалів (l (ui), l (ui+1)). Потім єдина лінійна перевірка визначить по яку сторону від ребра 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. Введемо позначення:

,

Покажемо, що ваги ребер можна обрати так, щоб виконувалися умови:

1. кожне ребро має додатню вагу;

2. для довільного vj (j \xF0B9 1, N) WIN (vj) = WOUT (vj).

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

Теорема. Реалізація умови WIN = WOUT є розв’язком потокової задачи і може бути досягнута за два проходи по графу G.

Покладемо спочатку W(e) = 1 для кожного ребра e. При першому проході від v1 до vN отримаємо WIN (vi) \xF0A3 WOUT (vi) для всіх некрайніх vi. При другому проході від vN до v1 отримаємо WIN (vi) \xF0B3 WOUT (vi). Отже після двох проходів матимемо реалізацію умови WIN (vi) = WOUT (vi).

Позначимо vIN (v) = | IN(v)|, vOUT (v) = | OUT(v)|.

Балансування за вагою в регулярному графі

begin