Геометричний пошук, Детальна інформація
Геометричний пошук
Перший прохід. Нехай 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 \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;
Другий прохід. Нехай 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 \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;
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021