WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Геометричний пошук - Реферат

Геометричний пошук - Реферат

кожна вершина лежить на границі смуги, то відрізки ребер всередині смуг не перетинаються. Тому ці відрізки можна впорядкувати зліва направо та використати двійковий пошук для визначення тієї трапеції (які можуть вироджуватися у трикутники), в яку попала точка z, витративши на це час O(log N). Оскільки смуга може містити O(N) відрізків, то час, необхідний на їх впорядкування, дорівнює O(N * log N).
Нехай k - кількість смуг планарного графа G. Позначимо через L список смуг, кожний елемент L[i] (1 i k) якого містить вказівник li на список відсортованих (зліва направо) відрізків у смузі.
Оскільки граф може мати O(N) смуг, а на впорядкування відрізків у кожній смузі витрачається час O(N * log N), тодля побудови структур даних L та li (1 i k) необхідно витратити час O(N2 * log N).
Локалізація точки методом смуг
1. Використовуючи y - координату точки z, методом бінарного пошуку у списку смуг L знайти смугу j, в якій лежить точка z.
2. Використовуючи x - координату точки z, методом бінарного пошуку у списку відрізків li знайти відрізки e1 та e2, між якими лежить точка z.
Витрати по пам'яті дорівнюють O(N2), оскільки існують такі планарні графи, сумарна кількість відрізків в полосах яких може досягати O(N2). Справа на малюнку біля кожної смуги вказано кількість відрізків, яка знаходиться в ній.
Якщо ребро графа проходить через декілька смуг, то ці смуги йдуть послідовно одна за іншою. Час передобробки можна скоротити якщо використати метод замітання площини.
Алгоритм плоского замітання характеризується двома основними структурами даних:
1. Список точок подій - послідовність позицій, що назначаються для замітаючої прямої.
2. Статус замітаючої прямої - опис перетину замітаючої прямої із замітаємим геометричним об'єктом.
Якщо замітання проводити знизу вгору, то моментальним статусом замітаючої прямої буде впорядкована зліва направо послідовність ребер графа, що перетинають ту смугу, де знаходиться замітаюча пряма. Ця послідовність (порядок ребер) не змінюється всередині смуги, але змінюється на границі з наступною смугою, коли досягається наступна вершина графа. Статус замітаючої прямої можна зберігати у формі дерева, збалансованого за висотою (2-3 дерева). Списком точок подій є перелічені знизу вгору вершини графа.
Передобробка. Побудова структур даних.
1. Відсортувати вершини графа G по зростанню y координати. Нехай відсортованим списком буде {v1, v2, ..., vn}. Побудуємо список L[i], з кожним елементом якого пов'яжемо дві точки vi та vi+1 графа G, одна з яких знаходиться на нижній границі смуги, а друга - на верхній. При цьому нехай вершина v0 має мінімальну y - координату, а vn+1 - максимальну y - координату. Умовоно орієнтуємо ребра графу G, які направлені від вершини з меншою y - координатою до вершини з більшою y - координатою.
2. Для смуги L[1] побудуємо порожнє 2 - 3 дерево T1. Список l1 покладемо порожнім.
3. k 2.
4. Розглянемо вершину vk-1 та видалимо всі вебра, які входять у vk-1 з дерева Tk-1 та вставимо у Tk-1 всі ребра, що виходять з vk-1. Отримали дерево Tk для L[k].
5. Обійдемо дерево Tk зліва направо, заносячи ребра до списку lk.
6. if k n then k k + 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) 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.
Loading...

 
 

Цікаве