Алгоритм Чена

Алгоритм Чена побудови опуклої оболонки. Трудомісткість $O(n\log h)$, $h$ — кількість точок у опуклій оболонці.

Алгоритм Чена — алгоритм побудови опуклої оболонки скінченної множини точок на площині. Виконується за час $O(n\log h)$, де $h$ — кількість точок опуклої оболонки. Є комбінацією алгоритму, що обчислює опуклу оболонку за час $O(n\log n)$ (наприклад, алгоритм Грехема) з алгоритмом загортання за Джарвісом, який виконується за час $O(nh)$.

Алгоритм широко використовується, так як є найшвидшим алгоритмом для обчислення опуклої оболонки, так і тому, що є суттєво простішим ніж алгоритм Кіркпатрика-Зейделя, який працює з такою ж швидкістю. Також узагальнюється на випадок обчислення опуклої оболонки в тривимірному просторі.

Алгоритм названий на честь Тімоті М. Чена.

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

Ідея алгоритму Чена полягає у початковому поділі всіх точок на групи по $m$ штук в кожній. Відповідно, кількість груп дорівнює $r=\left\lceil n/m\right\rceil$. Для кожної з груп будується опукла оболонка скануванням за Грехемом, або якимось іншим, що працює зі швидкістю $O(m\log m)$, таким чином, час витрачений для всіх груп точок складе $O(rm\log m)=O(n\log m)$.

Далі, починаючи з найнижчої точки (як що таких декілька, то обираємо з них крайню ліву), для отриманих в результаті розбиття оболонок будується спільна опукла оболонка за алгоритмом Джарвіса. При цьому наступна точка опуклої оболонки точка знаходиться за час $O(r\log m)$, так як для того, щоб знайти точку з максимальним тангенсом по відношенню до точки, що розглядається, в $m$-кутнику достатньо затратити $O(\log m)$. Логарифмічний час на пошук, витрачається тому, що точки в $m$-кутнику вже впорядковані за полярним кутом під час виконання алгоритму сканування за Грехемом. У підсумку, на обхід потрібно $O(hr\log m)=O\left(\left(hn/m\right)\log m\right)$ часу.

Тобто алгоритм Чена працює за $O\left(\left(n+hn/m\right)\log m\right)$, при цьому, якщо отримати $m=h$, то за $O(n\log h)$.

Hull(P, m)
 1)взяти $r=\left\lceil n/m\right\rceil$. Розділити $P$ на $r$ диз'юнктивних підмножин $P_{1},\;P_{2},\;\ldots ,\;P_{r}$ потужності не більше $m$;
 2)for i = 1 to r do:
     (a) обчислити опуклу оболонку Graham($P_{i}$), зберегти вершини в відсортованому за полярним кутом масиві;
 3)як $p_{1}$ взяти нижню найлівішу точку з $P$;
 4)for k = 1 to m do
     (a) for i = 1 to r do
             знайти та запам'ятати точку $q_{i}$ з $P_{i}$ з максимальним кутом $p_{k-1}p_{k}q_{i}$;
     (b) взяти як $p_{k+1}$ точку $q$ з ${q_{1},\;q_{2},\;\ldots ,\;q_{r}}$ с максимальним кутом $p_{k-1}p_{k}q$;
     (c) if $p_{k+1}=p_{1}$ return ${p_{1},\;\ldots ,\;p_{k}}$;
 5) return $m$ маленьке, спробуйте ще;

Вибір числа точок m

Зрозуміло, що обхід за Джарвісом, а отже і весь алгоритм, буде коректно працювати, тільки якщо $m\geqslant h$, але як заздалегідь дізнатися, скільки точок буде в опуклій оболонці? Треба запускати алгоритм декілька разів, підбираючи $m$ та, якщо $m<h$, то алгоритм буде повертати помилку. Якщо робити підбір бінарним пошуком за $n$, то у підсумку вийде час $O((n\log h)\log n)=O(n\log n)$, що достатньо довго.

Процес можна прискорити, якщо почати з маленького значення m і далі значно його збільшувати, доки не вийде $m\geqslant h$. З іншого боку, якщо m буде збільшуватись занадто швидко, то є ризик що m буде набагато більше h і буде виконана зайва робота, яка збільшить час роботи алгоритму. Ітерація на кроці з номером $t$ буде $m=\min(n,2^{2^{t}})$. При цьому $t$-а ітерація займе $O(n\log 2^{2^{t}})=O(n2^{t})$. Процес пошуку завершиться, коли $2^{2^{t}}\geqslant h$, тобто $t=\lceil \mathrm {log} \,\mathrm {log} \,h\rceil$ ($\log$ — бінарний логарифм).

У підсумку $\sum _{t=1}^{\mathrm {log} \,\mathrm {log} \,h}n2^{t}=n\sum _{t=1}^{\log \log h}2^{t}\leqslant n2^{1+\log \log h}=2n\log h=O(n\log h)$.

ChanHull(P)
 for t = 1 to n do:
     (a) взяти $m=\min(2^{2^{t}},\;n)$;
     (b) L = Hull(P, m);
     (c) if L != «$m$ маленьке, спробуйте ще» return L;

Реалізація

Стаття Чена містить декілька пропозицій, які можуть підвищити ефективність практичного використання алгоритму, наприклад:

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

Джерела

• David M. Mount. Computational Geometry. — University of Maryland, 2002. — С. 122.
• Timothy M. Chan. "Optimal output-sensitive convex hull algorithms in two and three dimensions [Архівовано 21 лютого 2008 у Wayback Machine.]". Discrete and Computational Geometry, Vol. 16, pp.361–368. 1996.