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

Алгоритм Чена — алгоритм построения выпуклой оболочки конечного множества точек на плоскости. Является комбинацией двух более медленных алгоритмов (сканирование по Грэхему $O(n\log n)$ и заворачивание по Джарвису $O(nh)$). Недостатком сканирования по Грэхему является необходимость сортировки всех точек по полярному углу, что занимает достаточно много времени $O(n\log n)$. Заворачивание по Джарвису требует перебора всех точек для каждой из $h$ точек выпуклой оболочки, что в худшем случае занимает $O(n^{2})$. Назван по имени Тимоти М. Чена.

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

Описание алгоритма

Идея алгоритма Чена заключается в изначальном делении всех точек на группы по $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\geqslant h$. Например, взять $2^{2^{t}}$. При этом $t$-я итерация займет $O(n\log 2^{2^{t}})=O(n2^{t})$. Процесс поиска завершится, когда $2^{2^{t}}\geqslant h$, то есть $t=\lceil \mathrm {lg} \,\mathrm {lg} \,h\rceil$ ($\mathrm {lg}$ — двоичный логарифм).

В итоге $\sum _{t=1}^{\mathrm {lg} \,\mathrm {lg} \,h}n2^{t}=n\sum _{t=1}^{\mathrm {lg} \,\mathrm {lg} \,h}2^{t}\leqslant n2^{1+\mathrm {lg} \,\mathrm {lg} \,h}=2n\,\mathrm {lg} \,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 с.