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

Алгоритм Чана (Тимоти М. Чан, 1996) — алгоритм построения выпуклой оболочки конечного множества точек на плоскости. Является комбинацией двух более медленных алгоритмов (сканирование по Грэхему $O(n \log n)$ и заворачивание по Джарвису $O(n h)$). Недостатком сканирования по Грэхему является необходимость сортировки всех точек по полярному углу, что занимает достаточно много времени $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(r m \log m) = O(n \log m)$ времени.

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

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