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

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

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

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

Идея алгоритма Чена заключается в изначальном делении всех точек на группы по ${\displaystyle m}$ штук в каждой. Соответственно, количество групп равно ${\displaystyle r=\left\lceil n/m\right\rceil }$. Для каждой из групп строится выпуклая оболочка сканированием по Грэхему за ${\displaystyle O(m\log m)}$, то есть для всех групп понадобится ${\displaystyle O(rm\log m)=O(n\log m)}$ времени.

Затем, начиная с самой левой нижней точки, для получившихся в результате разбиения оболочек строится общая выпуклая оболочка по Джарвису. При этом следующая подходящая для выпуклой оболочки точка находится за ${\displaystyle O(r\log m)}$, так как для того, чтобы найти точку с максимальным тангенсом по отношению к рассматриваемой точке в ${\displaystyle m}$-угольнике достаточно затратить ${\displaystyle O(\log m)}$ (точки в ${\displaystyle m}$-угольнике были отсортированы по полярному углу во время выполнения алгоритма сканирования Грэхема). В итоге, на обход требуется ${\displaystyle O(hr\log m)=O\left(\left(hn/m\right)\log m\right)}$ времени.

То есть алгоритм Чена работает за ${\displaystyle O\left(\left(n+hn/m\right)\log m\right)}$, при этом, если получить ${\displaystyle m=h}$, то за ${\displaystyle O(n\log h)}$.

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

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

Ясно, что обход по Джарвису, а следовательно и весь алгоритм, будет корректно работать только если ${\displaystyle m\geqslant h}$, но как заранее узнать, сколько точек будет в выпуклой оболочке? Надо запускать алгоритм несколько раз, подбирая ${\displaystyle m}$ и, если ${\displaystyle m<h}$, то алгоритм будет возвращать ошибку. Если делать подбор бинарным поиском по ${\displaystyle n}$, то в итоге получится время ${\displaystyle O((n\log h)\log n)=O(n\log n)}$, что достаточно долго.

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

В итоге ${\displaystyle \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) взять ${\displaystyle m=\min(2^{2^{t}},\;n)}$;
     (b) L = Hull(P, m);
     (c) if L != «${\displaystyle m}$ маленькое, попробуйте еще» return L;

Литература

• David M. Mount. Computational Geometry. — University of Maryland, 2002. — 122 с.