Алгоритм Кіркпатрика — Зейделя

Побудова опуклої оболонки методом «розділяй та володарюй» — алгоритм побудови опуклої оболонки зі швидкістю O(n log h), де n — кількість вхідних точок, та h — кількість точок в опуклій оболонці. Свою назву отримав від імен розробників — ^[en] та ^[en].

Опис алгоритму

Дано множина ${\displaystyle S}$, що складається з ${\displaystyle N}$ точок.

1. Якщо ${\displaystyle N\leqslant N_{0}}$ (${\displaystyle N_{0}}$ — деяке невелике ціле число), то побудувати опуклу оболонку одним з відомих методів та зупинитися, інакше перейти до кроку 2.
2. Розіб'ємо початкову множину ${\displaystyle S}$ довільним чином на два приблизно рівних за потужністю підмножини ${\displaystyle S_{1}}$ та ${\displaystyle S_{2}}$ (нехай ${\displaystyle S_{1}}$ містить ${\displaystyle [N/2]}$ точок, а ${\displaystyle S_{2}}$ містить ${\displaystyle N-[N/2]}$ точок).
3. Рекурсивно (п. 1) знаходимо опуклі оболонки кожної з підмножин ${\displaystyle S_{1}}$ та ${\displaystyle S_{2}}$.
4. Будуємо опуклу оболонку початкової множини опуклу оболонку об'єднанням двох опуклих оболонок ${\displaystyle CH(S_{1})}$ і ${\displaystyle CH(S_{2})}$.

Оскільки: ${\displaystyle CH(S)=CH(S1\cup S2)=CH(CH(S_{1})\cup CH(S_{2}))}$, складність цього алгоритму є рішенням рекурсивного співвідношення ${\displaystyle T(N)\leqslant 2T(N/2)+f(N)}$, де ${\displaystyle f(N)}$ — час побудови опуклої оболонки об'єднання двох опуклих багатокутників, кожний з яких має близько ${\displaystyle N/2}$ вершин. Далі буде показано, що ${\displaystyle T(N)=O(N\log N)}$.

Визначення

Опорною прямою до опуклого багатокутника ${\displaystyle P}$ називається пряма ${\displaystyle l}$, що проходить через деяку вершину багатокутника ${\displaystyle P}$ таким чином, що всі внутрішні точки багатокутника лежать по одну сторону від прямої ${\displaystyle l}$.

До опуклого багатокутнику ${\displaystyle P}$ можна побудувати опорні прямі з точки ${\displaystyle A}$, яка не належить йому. Скористаємося тим, що пряма ${\displaystyle AP_{i}}$, де ${\displaystyle P_{i}}$ — деяка вершина багатокутника ${\displaystyle P}$, є опорною до ${\displaystyle P}$ в тому і лише в тому випадку, якщо ребра ${\displaystyle (P_{i-1},P_{i})}$ і ${\displaystyle (P_{i},P_{i+1})}$ лежать в одній півплощині, обмеженою цією прямою. Неважко бачити, що для побудови опорних прямих потрібно в гіршому випадку один обхід вершин багатокутника ${\displaystyle P}$, тобто вони знаходяться за лінійний час.

Реалізація

Нехай ми вже маємо побудовані опуклі оболонки ${\displaystyle P_{1}}$ і ${\displaystyle P_{2}}$.

1. Знайдемо деяку внутрішню точку ${\displaystyle A}$ багатокутника ${\displaystyle P_{1}}$ (наприклад, центроїд будь-яких трьох вершин ${\displaystyle P_{1}}$). Така точка ${\displaystyle A}$ буде внутрішньою точкою ${\displaystyle CH(P_{1}\cup P_{2})}$.
2. Можливо два випадки:
   1. Точка ${\displaystyle A}$ не є внутрішньою точкою багатокутника ${\displaystyle P_{2}}$. Проводимо дві опорні прямі для багатокутника ${\displaystyle P_{2}}$, що проходять через точку ${\displaystyle A}$. Ці опорні прямі проходять через вершини ${\displaystyle B}$ і ${\displaystyle C}$ багатокутника ${\displaystyle P_{2}}$. Всі точки всередині трикутника ${\displaystyle ABC}$ не належить границі опуклої оболонки ${\displaystyle CH(P1\cup P2)}$. Всі інші точки упорядковуємо по полярному куту щодо точки ${\displaystyle A}$, злиттям двох упорядкованих списків вершин за час ${\displaystyle O(N_{1})+O(N_{2})=O(N)}$, а потім застосовуємо до отриманого списком метод обходу Грехема, що вимагає лише лінійний час.
   2. Точка ${\displaystyle A}$ є внутрішньою точкою багатокутника ${\displaystyle P_{2}}$. Упорядковуємо вершини обох багатокутників щодо центру ${\displaystyle A}$, зливаючи два впорядкованих списку вершин ${\displaystyle P_{1}}$ і ${\displaystyle P_{2}}$ за ${\displaystyle O(N)}$.
3. Тепер до отриманого списком вершин можна застосувати алгоритм Грехема за винятком фази сортування точок по полярній координаті, тоді він буде виконаний за лінійний час.

Тепер отримана опукла оболонка об'єднання опуклих багатокутників ${\displaystyle P_{1}\cup P_{2}}$.

Складність алгоритму

У сумі всі три фази алгоритму виконуються за час ${\displaystyle O(N)}$. Таким чином, ${\displaystyle f(N)=O(N)}$ і отримуємо співвідношення ${\displaystyle T(N)\leqslant 2T(N/2)+O(N)}$, рішенням якого, як відомо, є ${\displaystyle T(N)=O(N\log N)}$, що і визначає складність алгоритму.

Примітки

1. Kirkpatrick, David G.; (1986). The ultimate planar convex hull algorithm. . 15 (1): 287—299. doi:10.1137/0215021.

Посилання

• http://www.cs.umd.edu/~samir/754/kshand.ps [ 21 квітня 2013 у Wayback Machine.](англ.)