Попередня Змiст Наступна

3.3.1. Метод смуг

  Нехай задано плоский прямолінійний граф G. Проведемо горизонтальні прямі через кожну його вершину. Вони розділятимуть площину на (N+1) горизонтальні смуги. Якщо провести сортування цих смуг за координатою y, то можна знайти ту смугу, в якій лежить точка z, за час O(log N) (Мал. 3.8).
  Враховуючи упорядкованість відрізків для визначення тієї трапеції, в яку потрапила точка z, можна скористатись двійковим пошуком з часом O(log N). Звідси отримаємо оцінку часу запиту для найгіршого випадку: O(log N).
Мал. 3.8. Вершини плоского прямолінійного графа визначають смуги.
Тепер розглянемо перетин однієї зі смуг із графом G. Перетин складається з відрізків ребер графа G. Ці відрізки визначають трапеції (трапеції можуть вироджуватися в трикутники). Оскільки G планарний граф, то його ребра перетинаються між собою тільки в вершинах, а так як кожна вершина лежить на межі смуги, то відрізки ребер всередині смуги не перетинаються (мал. 3.9).
Мал. 3.9. Відрізки ребер графа всередині смуги не перетинаються.
  Попередня обробка. Сортуються всі відрізки всередині кожної смуги: O(N2 log N) - для часу і O(N2) - для пам'яті. Час попередньої обробки можна скоротити до O(N2). Однак існують такі плоскі прямолінійні графи, які потребують квадратичної пам'яті (мал. 3.10).
Мал. 3.10. Сумарне число відрізків на смугах може доосягати O(N2).
Метод плоского замітання (МПЗ)
Метод плоского замітання характеризується основними структурами даних:
  1. Списком точок подій - послідовністю позицій, які призначені для замітаючої прямої;
  2. Статусом замітаючої прямої - опис перетину замітаючої прямої з геометричним об'єктом, який замітають.
  У методі смуг список точок подій - це просто перелік знизу вгору смуг, які відповідають вершинам плоского прямолінійного графу. Статус - це послідовність відрізків(ребер графа) всередині смуги, що розташована вище (мал. 3.11).
  Витрати ресурсів:
  1. вставка та вилучення кожного із ребер графа - складність O(log N) на одну операцію;
  2. запам'ятовування статусу. (На першу операцію піде O(N log N) часу; на другу- O(N2)).
{Ø}
{e1, e2}
{ e2, e3, e4, e5}{ e2, e4, e5, e6, e7 }
{ e2, e4, e5, e6, e7, e9, e10}
вст.
вст.  
вст.
вст.
вст.
{Ø}
{e1, e2}
{ e3, e4, e5}
{ e6, e7 }
{ e6, e7 }
вил.
вил.
вил.
вил.
вил.
{Ø}
{Ø}
{e1 }
{e3 }
{Ø}
Мал.3.11
  Теорема 3.4. Локалізацію точки в N-вершинному планарному розбитті МПЗ можна реалізувати за час O(log N) з використанням O(N2) пам'яті, якщо O(N2) часу пішло на обробку.


Попередня Змiст Наступна