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

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

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

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

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

3. Rj \xF0C7\xF020Rk \xF0B9\xF020\xF0C6.

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

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

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

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

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

begin

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

else

begin

v \xF0AC\xF020корінь;

while (Г(v) \xF0B9\xF020\xF0C6) do

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

if (z \xF0CE ТРИКУТНИК(u)) then v \xF0AC u;

друк v;

end;

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.