Реферат на тему:

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

Означення. Пошукове повідомлення, у відповідності з яким ведеться
перегляд файла, називається запитом.

Нехай є набір геометричних даних і треба встановити, чи мають вони певну
властивість. Якщо запит виникає один раз, то його будемо називати
унікальним. Запити, обробка яких повторюється декілька разів в одному і
тому ж файлі, називаються масовими.

Міри оцінки запиту:

1. Час запиту. Скільки часу необхідно в середньому, у найкращому та
найгіршому випадках.

2. Пам’ять. Скільки пам’яті необхідно для зберігання структури даних.

3. Час передобробки. Скільки часу необхідно для організації даних перед
пошуком.

4. Час корегування. Дано елемент даних. Який час необхідно використати
на його видалення чи вставку до структури даних.

Означення. Передобробкою будемо називати процес розташування даних у
зручній для подальшої обробки структурі даних.

Задача. Геометричний пошук. Дано планарний граф G з N вершинами та точка
z. Необхідно встановити область графу G, в якій розташована точка z.

Час передобробки не може бути меншим за O(N), оскільки навіть процес
читання вершин вимагає час O(N). Витрати по пам’яті не можуть бути
меншими за O(N) при зберіганні у довільній структурі даних, оскільки
навіть для зберігання самого графа G вимагаються витрати по пам’яті
O(N). Запит до структури даних, яка містить N елементів, вимагає як
мінімум часу O(N * log N).

Регіональний пошук

Задача. Регіональний пошук. Дано N точок на площині. Скільки точок
лежить всередині заданого прямокутника, сторони якого паралельні
координатним осям? Тобто скільки точок (x, y) задовольняє нерівностям a
??x ??b, c ??y ??d для заданих a, b, c, d?

Метод локусів. (Локус – це застарілий термін “геометричне місце точок”).
Запиту ставиться у відповідність точка у зручному для пошуку просторі, а
цей простір розбивається на області (локуси), в межах яких відповідь не
змінюється.

Означення. Точка (вектор) v домінує над w тоді і тільки тоді коли для
усіх індексів i справедлива умова vi ??wi.

Q(P1) = 14, Q(P2) = 9, Q(P3) = 1, Q(P4) = 2. N(P1P2P3P4) = 14 — 9 — 2 +
1 = 4

На площині точка v домінує над w тоді і тільки тоді коли w лежить у
лівому нижньому квадранті, що визначається v. Позначимо через Q(p)
кількість точок, над якими домінує p. Кількість точок N(p1p2p3p4) у
прямокутнику p1p2p3p4 визначається наступним чином:

N(p1p2p3p4) = Q(p1) — Q(p2) — Q(p4) + Q(p3)

Задачу регіонального пошуку зведено до задачі обробки запитів про
домінування для чотирьох точок. Опустимо із заданих точок на вісі x та y
перпендикуляри, а отримані лінії продовжимо у нескінченність. Утворилася
решітка з (N + 1)2 прямокутників.

Теорема. Часови оцінки запропонованого алгоритму: пердобробка – O(N2),
пам’ять – O(N2), запит – O(log N).

Задачі локалізації точки

Задача. Належність точки простому многокутнику. Дано простий многокутник
(N — кутник) P та точка z. Чи знаходиться точка z в середині P?

Алгоритм. Проведемо через точку z горизонталь l. Якщо l не перетинає P,
то z – зовнішня точка. Припустимо, що l перетинає P та не проходить
через жодну його вершину. Нехай L – кількість точок перетину прямої l з
границею P зліва від z. Очевидно, що точка z лежить всередині
многокутника тоді і тільки тоді, коли L непарне.

Якщо пряма проходить через вершини многокутника, то при обчисленні
значення L необхідно користуватися наступними правилами: якщо обидві
вершини ребра належать l, то це ребро треба відкинути; якщо тільки одна
вершина ребра лежить на l, то перетин враховується, якщо це вершина з
більшою ординатою та ігнорується інакше.

Належність простому многокутнику

begin

L ??0;

for i ??1 to N do

if ( ребро ( i ) не горизонтальне) then

if ( ребро( i ) перетинає l нижнім кінцем зліва від z)

then L ??L + 1;

if (L непарне) then z всередині else z ззовні;

end.

Теорема. Належність точки z внутрішній області простого N — кутника
можна встановити за час O(N) без передобробки.

Задача. Належність точки опуклому многокутнику. Дано опуклий многокутник
(N — кутник) P та точка z. Чи знаходиться точка z в середині P?

Алгоритм. Вершини опуклого многокутника впорядкуємо за полярними кутами
відносно довільної внутрішньої точки q, в якості якої можна взяти,
наприклад, центр ваги довільних трьох вершин P. Проведемо N променів з
точки q через вершини многокутника. Ці промені розіб’ють площину на N
клинів, кожен з яких розбивається стороною многокутника на дві частини.
За допомогою двійкового пошуку можна знайти клин, в якому лежить точка z
(промені розташовані в порядку зростання їх полярних кутів проти
годинникової стрілки). Точка z лежить між променіми pi та pi+1 тоді і
тільки тоді, коли кут (zqpi+1) додатний, а кут (zqpi) від’ємний. Коли
точки pi та pi+1 знайдено, то точка z буде внутрішньою тоді і тільки
тоді, коли кут (pipi+1z) від’ємний.

Теорема. Час відповіді на запит про належність точки опуклому N —
кутнику дорівнює O(log N) при затраті O(N) пам’яті та O(N) часу на
попередню обробку.

Попередня обробка полягає в розташуванні вершин многокутника в структурі
даних, придатної для двійкового пошуку.

Зірчасті многокутники є більш обширним класом простих многокутників, що
включають в себе опуклі многокутники. Зірчастий многокутник містить хоча
б одну таку точку q, що відрізок qpi повністю лежить всередині
многокутника P для довільної вершини pi. Множина всіх можливих таких
точок q називається ядром P. Після знаходження такої точки q можна
використовувати попередній алгоритм.

Теорема. Час відповіді на запит про належність точки зірчастому N —
кутнику дорівнює O(log N) при затраті O(N) пам’яті та O(N) часу на
попередню обробку.

Локалізація точки на планарному розбитті

Метод смуг. Нехай задано планарний граф G. Проведемо горизонтальні прямі
через кожну його вершину. Ці прямі розіб’ють площину не більш ніж на N +
1 горизонтальних смуг. Відсортуємо ці смуги за координатою y, після чого
можна знайти ту смугу, в якій знаходиться задана точка z за час O(log
N).

Знайдена смуга перетинає відрізки ребер графа G. Оскільки G є плоске
укладання планарного графа, то його ребра перетинаються між собою лише у
вершинах, а оскільки кожна вершина лежить на границі смуги, то відрізки
ребер всередині смуг не перетинаються. Тому ці відрізки можна
впорядкувати зліва направо та використати двійковий пошук для визначення
тієї трапеції (які можуть вироджуватися у трикутники), в яку попала
точка 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) < 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 ? 1, N) WIN (vj) = WOUT (vj). Перша умова встановлює факт належності кожного ребра хоча б одному ланцюгу. Друга умова гарантує, що WIN (vj) ланцюгів проходить через vj і їх можна обрати так, щоб вони не перетиналися. Теорема. Реалізація умови WIN = WOUT є розв’язком потокової задачи і може бути досягнута за два проходи по графу G. Покладемо спочатку W(e) = 1 для кожного ребра e. При першому проході від v1 до vN отримаємо WIN (vi) ? WOUT (vi) для всіх некрайніх vi. При другому проході від vN до v1 отримаємо WIN (vi) ? WOUT (vi). Отже після двох проходів матимемо реалізацію умови WIN (vi) = WOUT (vi). Позначимо vIN (v) = | IN(v)|, vOUT (v) = | OUT(v)|. Балансування за вагою в регулярному графі begin for кожне ребро з e do W(e) ??1; /* ініціалізація */ for i ??2 to N - 1 do begin WIN (vi) ??сума ваг ребер, що входять у vi; d1 ??крайнє зліва ребро, що виходить з vi; if (WIN (vi) > vOUT (vi)) then W(d1) ??WIN (vi) — vOUT (vi) + 1;

end; /* перший прохід */

for i ??N — 1 downto 2 do

begin

WOUT (vi) ??сума ваг ребер, що виходять з vi;

d2 ??крайнє зліва ребро, що входить у vi;

if (WOUT (vi) > WIN (vi)) then W(d2) ??WOUT (vi) — WIN (vi) + W(d2);

end; /* другий прохід */

end.

нумерація вершин та ініціалізація ребер перший прохід

другий прохід повна множина ланцюгів

Приклад.

Перший прохід. Нехай i = 6 (ваги всіх ребер, що виходять з k — ої (k < 6) вершини, вже розставлені). WIN (v6) = 4 (вхідними є ребра: 36 – вага 1, 46 – вага 1, 56 – вага 2). Ребра, що виходять з v6: 67, 69. d1 = 69 (крайнє зліва ребро). vOUT (v6) = 2, WIN (v6) > vOUT (v6), тому що 4> 2.
W(69) = 4 — 2 + 1 = 3.

Другий прохід. Нехай i = 3. WOUT (v3) = 3. Ребра, що входять у v3: 13.
d2 = 13 (крайнє зліва ребро). W(13) = 1. WIN (v3) = 1. WOUT (v3) > WIN
(v3), тому що 3 > 1. W(13) = 3 — 1 + 1 = 3.

Теорема. Довільний планарний граф можна перетворити в регулярний.

Доведення. Нехай v – нерегулярна вершина графа G. Припустимо, що з неї
не виходить жодного ребра. Горизонтальна пряма, що проходить через v,
протикає в загальному випадку пару ребер e1 та e2 графа G, найближчих до
v зліва та справа. Оскільки v не є крайньою вершиною, то один з цих
проколів повинен існувати. Нехай vi – верхня вершина ребер ei (i = 1,
2), а v* – та з вершин vi, що має найменшу ординату (наприклад, v2).
Тоді відрізок vv* не перетинає ребер G (в загальному випадку це не вірно
і тоді алгоритм регуляризації слід змінити) і може бути доданим до ребер
планарного графу, регуляризуючи вершину v.

Використуючи алгоритм плоского замітання, замітаємо граф згори вниз
регуляризуючі вершини, які не мають вихідних ребер, а потім знизу вгору
для регуляризації вершин іншого типу.

регуляризований планарний граф

Теорема. N вершинний планарний граф можна регуляризувати за час O(N *
log N) з витратами пам’яті O(N).

Теорема. Локалізацію точки в N вершинному планарному підрозбитті можна
реалізувати за час O(log2 N) з використанням O(N) пам’яті при затраті
часу O(N * log N) на передобробку.

Метод деталізації триангуляції Кіркпатріка

Нехай задана N вершинна триангуляція G. Побудуємо послідовність
триангуляцій S1, S2, …, Sh(N), де S1 = G, а Si отримується з Si-1 за
наступними правилами:

Крок 1. Видалимо деяку множину незалежних (несуміжних) неграничних
вершин Si-1 та інцидентні їм ребра.

Крок 2. Будуємо триангуляцію утворених многокутників.

Таким чином Sh(N) не має внутрішніх вершин і складається з єдиного
трикутника. Всі триангуляції мають одну спільну границю. Припустимо, що
трикутник Rj належить триангуляції Si (позначатимемо Rj ??*Si), якщо Rj
створено на другому кроці при побудові Si.

Нехай T – структура даних для пошуку, вузлам якої відповідають
трикутники. Структура Т, топологію якої представляє направлений
ациклічний граф, визначається наступним чином: від трикутника Rk до
трикутника Rj проводиться дуга, якщо при побудові Si після Si-1 маємо:

1. Rj видаляється з Si-1 на кроці 1;

2. Rk утворюється з Si на кроці 2;

3. Rj ??Rk ???.

Трикутники з Si не мають вихідних дуг.

Початковий крок полягає в локалізації точки z відносно Sh(N). Потім
рухаємося вниз по шляху в Т до одного з трикутників з S1. Відбувається
послідовна локалізація точки z у триангуляціях Sh(N), Sh(N) — 1, …,
S1. Факт, що Si-1 є результатом деталізації Si, пояснює назву метода.

Структура даних T – направлений ациклічний граф пошуку

Позначимо через ТРИКУТНИК(v) трикутник, який відноситься до вузла v. Усі
потомки вузла v зберемо у список Г(v).

деталізація трикутника

begin

if (z ??ТРИКУТНИК(корінь)) then друк “z лежить у нескінченній області“;

else

begin

v ??корінь;

while (Г(v) ???) do

for кожний u ? Г(v) do

if (z ? ТРИКУТНИК(u)) then v ? u;

друк v;

end;

end.

Припустимо, що множину вершин на першому кроці методу деталізації можна
вибрати так, щоб виконувалися наступні властивості (через Ni позначимо
кількість вершин в Si):

1. Ni = aiNi-1, де ai ??a < 1 для i = 2, ..., h(N). 2. Кожний трикутник Rj ??Si перетинається не більш ніж з H трикутниками з Si-1 та навпаки. Критерій вибору вершин. Видалити несуміжні вершини зі степінем, меншим K, де K – ціле число, що підбирається. Порядок перегляду та видалення вершин наступний: почнемо з довільної вершини, помічаємо її сусідів (які не можуть видалятися на поточному кроці) і продовжуємо далі поки ще є непомічені сусіди. Теорема. Локалізацію точки в N вершинному планарному підрозбитті можна реалізувати за час O(log N) з використанням O(N) пам’яті при затраті часу O(N * log N) на передобробку. Метод трапецій Означення. Трапеція має дві горизонтальні сторони та може мати дві, одну або нуль бокових сторін, причому бокові сторони є ребрами планарного графу G і жодне інше ребро G не перетинає обидві її горизонтальні сторони. Означення. Дано два ребра e1 та e2 з E. Запис e1 < e2 означає що існує горизонталь, яка перетинає обидва ребра, і точка її перетину з e1 знаходиться лівіше за точку перетину з e2. Механізм побудови структури даних пошуку обробляє по одній трапеції та намагається розбити її на максимально можливу кількість менших трапецій. Це відбувається шляхом розрізання трапеції R на нижню R1 та верхню R2 горизонтальною прямою, яка є медіаною множини ординат вершин всередині R. Означення. Якщо ребро графа G перетинає обидві горизонтальні сторони трапеції, то воно називається накриваючим. Після визначення медіани ymed трапеції R множина ребер графа G, яка перетинає R, проглядається зліва направо та розділяється на дві множини, що відносяться до R1 та R2. Якщо зустрічається накриваюче ребро, то воно стає правою боковою границею нової трапеції, яка обробляється незалежно. Розбиття трапеції Кожній трапеції R відповідає дерево двійкового пошуку T(R), пожен вузол якого пов’язано з лінійною перевіркою. Вузли можуть бути двох типів: ??- вузли, якщо перевірка відбувається відносно горизонталі, та О - вузли, якщо перевірка відбувається відносно прямої, яка містить ребро графа. Корінь завжди є ??- вузлом. Оскільки дві крайні вершини графа не беруть участі у розбитті трапеції, то кількість ? - вузлів у дереві пошуку дорівнює N - 2. Дерево пошуку, яке відповідає трапеції d c b a y(p)d P2 P1 P4 P3 x(p) 5 4 3 2 1 2 2 1 1 3 1 1 1 1 1 0 0 0 0 0 0 0 0 0 l P z P3 P2 q P4 z P1 P5 P q Z Z 2 4 6 8 10 u1 u2 l u4 u3 l(u1) l(u2) l(u3) u5 l(u4) l(u5) 9 1 2 8 3 7 1 1 2 6 1 1 1 1 5 1 4 1 1 1 3 1 1 2 1 9 1 1 8 1 7 1 1 1 6 1 1 1 1 5 1 4 1 1 1 3 1 1 2 1 9 1 2 8 3 7 1 1 2 6 1 1 1 1 5 1 4 1 1 1 3 1 3 2 1 v2 = v* v1 e1 v e2 8 10 ???????????????????????????????????????????????????????????????????????? ??????????????? медіана R3 e2 R2 R6 R7 верхній шар нижній шар нижче вище справа зліва справа зліва зліва справа T(R6) T(R7) T(R3) T(R5) T(R4) e1 e2 e3

Похожие записи