WikiSort.ru - Не сортированное

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

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

Идея алгоритма Чана заключается в изначальном делении всех точек на группы по ${\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 с.