Геометричний пошук

Теорема. Задачу локалізації точки методом смуг можна виконати за час 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. Введемо позначення:

WIN (v) = , WOUT (v) = ,

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

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

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