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

4.8. Побудова опуклої оболонки простого многокутника.

4.8.1. Алгоритм апроксимації опуклої оболонки

При знаходженні наближеної опуклої оболонки ми розмінюємо точність на простоту та ефективність алгоритму.
Мал. 4.20. Апроксимація опуклої оболонки.
Такий алгоритм може бути корисним для застосувань, в яких необхідно швидко знайти розв'язок. Так, зокрема, у прикладній статистиці, де результати спостережень відомі з деякою визначеною мірою точності. Розглянемо один із таких алгоритмів.
Основна ідея алгоритму полягає в тому, щоб виділити із заданої множини точок S деяку підмножину S*, опукла оболонка якої являє собою апроксимацію опуклої оболонки заданої множини.
Побудова.
  1. Визначаються чотири екстремальні точки: , , , . Вибираємо точки, які мають мінімальну та максимальну х-кординати: xmax, xmin. Вертикальна смуга між ними розбивається на k смуг рівної ширини. (Ці k смуг утворюють послідовність "комірок", по яким будуть розподілятись N точок множини S.)
  2. В кожній із цих k смуг визначаються точки з екстремальними у-координатами: ( 2k точок).
  3. Множини точок з екстремальними координатами 1-ої та к-ої смуг такі (максимум 4 точки): , . Сформована множина містить не більше 2k + 4 точок, позначимо її через S*.
  4. Будується опукла оболонка множини S*, яка є апроксимацією оболонки заданої множини S, одним із відомих методів (наприклад, методом Грехема).
Реалізація методу.
  1. Вказані k смуг відображаються в масиві із (k+2) елементів(0-й та (k+1)-й елементи містять дві точки із екстремальними значеннями х-координати: відповідно (xmin, xmax)).
  2. Смуга (номер смуги i), у яку потрапляє деяка точка р, визначається співвідношенням: , де D = (xmax - xmin)/k.
  3. Мінімум та максимум у кожній смузі можна визначати паралельно.
  4. Для побудови упорядкованої множини точок порівнюємо у кожній смузі значення х - координати двох точок множини S*, які належать цій смузі. Повний час роботи алгоритму рівний Q( N + k ).
Питання. Як далеко від наближеної опуклої оболонки може бути точка із S, яка розташована за її межами?
Відповідь на це питання дає наступна теорема.
Теорема 4.11. Довільна точка p S, яка не потрапила всередину наближеної опуклої оболонки, розташована на відстані, не більшій ніж D=(xmax - xmin) / k.
Доведення. Розглянемо смугу, яка містить точку р. Так як точка р розташована за межами наближеної оболонки, то вона не може мати ні найбільшу, ні найменшу у-координату серед точок, які потрапили у цю ж смугу ymin y(p) ymax. Якщо u - це точка перетину горизонтальної прямої, яка проходить через точку р, з ребром наближеної оболонки, то довжина відрізка pu обмежує зверху відстань від точки р до оболонки. Довжина відрізку pu сама обмежена зверху шириною смуги (D =(xmax - xmin) / k).
Мал. 4.21. Аналіз алгоритму апроксимації.


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