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

Алгоритм Чена — алгоритм построения выпуклой оболочки конечного множества точек на плоскости. Является комбинацией двух более медленных алгоритмов ( сканирование по Грэхему $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;