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

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

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

Теорема. 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