Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Чана

Алгоритм Чана — алгоритм построения выпуклой оболочки конечного множества точек на плоскости. Является комбинацией двух более медленных алгоритмов и заворачивание по Джарвису O). Недостатком сканирования по Грэхему является необходимость сортировки всех точек по полярному углу, что занимает достаточно много времени O. Заворачивание по Джарвису требует перебора всех точек для каждой из h точек выпуклой оболочки, что в худшем случае занимает O.

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

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

Идея алгоритма Чана заключается в изначальном делении всех точек на группы по m штук в каждой. Соответственно, количество групп равно . Для каждой из групп строится выпуклая оболочка сканированием по Грэхему за O, то есть для всех групп понадобится O = O времени.

Затем, начиная с самой левой нижней точки, для получившихся в результате разбиения оболочек строится общая выпуклая оболочка по Джарвису. При этом следующая подходящая для выпуклой оболочки точка находится за O, так как для того, чтобы найти точку с максимальным тангенсом по отношению к рассматриваемой точке в m-угольнике достаточно затратить O. В итоге, на обход требуется времени.

То есть алгоритм Чана работает за , при этом, если получить m = h, то за O.

Hull
 1)взять . Разделить P на r дизъюнктных подмножеств  мощности не более m;
 2)for i = 1 to r do:
     вычислить выпуклую оболочку Graham, сохранить вершины в отсортированном по полярному углу массиве;
 3)в качестве p1 взять самую левую и нижнюю точку из P;
 4)for k = 1 to m do
     for i = 1 to r do
             найти и запомнить точку qi из Pi с максимальным углом pk − 1pkqi;
     взять в качестве pk + 1 точку q из  с максимальным углом pk − 1pkq;
     if pk + 1 = p1 return ;
 5) return m маленькое, попробуйте еще;