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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Описание алгоритма[править | править код]

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

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

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

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

Выбор числа точек m[править | править код]

Ясно, что обход по Джарвису, а следовательно и весь алгоритм, будет корректно работать только если , но как заранее узнать, сколько точек будет в выпуклой оболочке? Надо запускать алгоритм несколько раз, подбирая и, если , то алгоритм будет возвращать ошибку. Если делать подбор бинарным поиском по , то в итоге получится время , что достаточно долго.

Процесс можно ускорить, если начать с маленького значения и после значительно его увеличивать, пока не получится . Например, взять . При этом -я итерация займет . Процесс поиска завершится, когда , то есть ( — двоичный логарифм).

В итоге .

ChanHull(P)
 for t = 1 to n do:
     (a) взять ;
     (b) L = Hull(P, m);
     (c) if L != « маленькое, попробуйте еще» return L;

Литература[править | править код]

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