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

Дано множина ${\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)}$, що і визначає складність алгоритму.

• http://www.cs.umd.edu/~samir/754/kshand.ps(англ.)