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

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

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

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

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

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

Визначення ред.

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

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

Реалізація ред.

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

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

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

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

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

Примітки ред.

↑ Kirkpatrick, David G.; Seidel, Raimund (1986). The ultimate planar convex hull algorithm. SIAM Journal on Computing. 15 (1): 287—299. doi:10.1137/0215021.

Посилання ред.

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

[1] Kirkpatrick, David G.; Seidel, Raimund (1986). The ultimate planar convex hull algorithm. SIAM Journal on Computing. 15 (1): 287—299. doi:10.1137/0215021.

[1]