Опукла оболонка, Детальна інформація

Теорема. Опукла оболонка простого многокутника з N вершинами може бути побудована за оптимальний час O(N) з використанням пам’яті об’ємом O(N).

Динамічні алгоритми побудови опуклої оболонки

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

Означення. Часовий проміжок між вводом двох послідовних елементів даних називається затримкою надходження даних.

Задача. Відкритий алгоритм для опуклої оболонки. На площині задана послідовність N точок p1, p2, ..., pN. Необхідно знайти їх опуклу оболонку таким чином, щоб після обробки точки pi була побудована CH(p1, p2, ..., pi). Алгоритм повинен підтримувати деяке представлення поточної опуклої оболонки та коректувати його по мірі надходження точок.

Якщо не брати до уваги часову оцінку, то можна запропонувати наступний алгоритм:

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

2. Підтримувати зв’язаний список впорядкованих крайніх точок. При надходженні точки pi вставити її у список відповідно до її полярного кута, витративши час O(i).

3. Виконати перегляд зв’язаного списку крайніх точокметодом Грехема. Можливі три варіанти цього кроку:

а) точка pi є крайньою і її включення викликає видалення деяких інших точок;

б) точка pi є крайньою, але її включення не викликає видалення інших точок;

в) точка pi є внутрішньою і тому вона видаляється.

Теорема. Довільний відкритий алгоритм побудови опуклої оболонки в найгіршому випадку повинен витрачувати на обробку між надходженням послідовних елементів даних час O(log N).

Ефективність відкритого алгоритму полягає у можливості швидко будувати дві опорні прямі до опуклого многокутника, що проходять через задану точку. Позначимо через Ci-1 опуклу оболонку множини {p1, p2, ..., pi-1}. Необхідно побудувати з точки pi опорні прямі до Ci-1, якщо вони існують (коли pi є зовнішньою для Ci-1). Будемо називати опорну пряму лівою чи правою в залежності від того, по яку сторону вона знаходиться якщо дивитися з точки pi на Ci-1.

Означення. Вершина v називається вогнутою, якщо відрізок pv перетинає внутрішню частину многокутника. Якщо дві суміжні з v вершини лежать по одну сторону від прямої, що проходить через p та v, то вершина називається опорною. Інакше вершина називається опуклою.

Якщо v – опорна вершина, то розв’язок задачі завершується. Інакше будуємо опорні прямі. Для знаходження, наприклад, лівої опорної прямої, необхідно рухатися по вершинам многокутника проти чи за годинниковою стрілкою (в залежності від опуклості чи вогнутості вершини v). Таким чином визначаються дві опорні точки.

Теорема. Опукла оболонка множини з N точок на площині може бути побудована за допомогою відкритого алгоритму за час O(N * log N) з часом корекції O(log N).

v

p + v

p

q

p - q

p

u + v

v

u

Aff(p, q, 0)

Aff(p, q, -1/2)

Aff(p, q, 1/2)

Aff(p, q, 1)