WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Геометричний пошук - Реферат

Геометричний пошук - Реферат

Оскільки vj регулярна, то існує таке i 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 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.
Дерево пошуку, яке відповідає трапеції
Loading...

 
 

Цікаве