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

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

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

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

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

Hull(P, m)

1)взять . Разделить P на r дизъюнктных подмножеств мощности не более m;

2)for i = 1 to r do:

(a) вычислить выпуклую оболочку Graham(Pi), сохранить вершины в отсортированном по полярному углу массиве;

3)в качестве p1 взять самую левую и нижнюю точку из P;

4)for k = 1 to m do

(a) for i = 1 to r do

найти и запомнить точку qi из Pi с максимальным углом pk − 1pkqi;

(b) взять в качестве pk + 1 точку q из с максимальным углом pk − 1pkq;

(c) if pk + 1 = p1 return ;

5) return m маленькое, попробуйте еще;

Ясно, что обход по Джарвису, а следовательно и весь алгоритм, будет корректно работать только если , но как заранее узнать сколько точек будет в выпуклой оболочке? Надо запускать алгоритм несколько раз, подбирая m и, если m < h, то алгоритм будет возвращать ошибку. Если делать подбор бинарным поиском по n, то в итоге получится время O((nlog h)log n) =O(nlog n), что достаточно долго.

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

В итоге .

ChanHull(P)

for t = 1 to n do:

(a) взять ;

(b) L = Hull(P, m);

(c) if L != «m маленькое, попробуйте еще» return L;

Лит.: David M. Mount Computational Geometry — University of Maryland, 2002. — С. 122.