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

end.

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

1. Ni = aiNi-1, де ai \xF0A3\xF020a < 1 для i = 2, ..., h(N).

2. Кожний трикутник Rj \xF0CE\xF020Si перетинається не більш ніж з 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), пожен вузол якого пов’язано з лінійною перевіркою. Вузли можуть бути двох типів: \xF0D1\xF020- вузли, якщо перевірка відбувається відносно горизонталі, та О - вузли, якщо перевірка відбувається відносно прямої, яка містить ребро графа. Корінь завжди є \xF0D1\xF020- вузлом. Оскільки дві крайні вершини графа не беруть участі у розбитті трапеції, то кількість \xF0D1 - вузлів у дереві пошуку дорівнює N - 2.

Дерево пошуку, яке відповідає трапеції

d

c

b

a

y(p)d

P2

P1

P4

P3

x(p)

5

4

3

2

1