= Алгоритм Чена =
ХерняЯвляется комбинацией двух алгоритмов - Джарвиса и Грехема. Недостатком Грэхема является необходимость сортировки всех точек по полярному углу, что занимает достаточно много времени <tex>O(n \log n)</tex>. Джарвис требует перебора всех точек для каждой из <tex>k</tex> точек оболочки, что в худшем случае занимает <tex>O(n^2)</tex>. == Описание Алгоритма == 1)Разобьем все множество на произвольные группы по <tex>m</tex> штук в каждой. Будем считать, что <tex>m</tex> нам известно. Тогда всего групп окажется <tex>r = n / m</tex>. 2)Для каждой группы запускаем Грехема. 3)Начиная с самой нижней точки ищем саму выпуклую оболочку Джарвисом, но перебираем не все точки, а по одной из каждой группы. == Сложность == На втором шаге алгоритма в каждой группе оболочка ищется за <tex>O(m \log m)</tex>, общее время - <tex>O(r m \log m) = O(n \log m)</tex>. На третьем шаге поиск каждой следующей точки в каждой группе занимает <tex>O(\log m)</tex>, так как точки уже отсортированы, и мы можем найти нужную бинпоиском. Тогда поиск по всем группам займет <tex>O(r \log m) = O(n / m \log m)</tex>. Всего таких шагов будет <tex>k</tex>, значит общее время - <tex>O(k n / m \log m)</tex>.Итоговое время - <tex>O(n (1 + k / m) \log m)</tex>. Несложно видеть, что минимум достигается при <tex>m = k</tex>. В таком случае сложность равна <tex>O(n \log k)</tex>. == Поиск <tex>m</tex> == Как заранее узнать <tex>k</tex>? Воспользуемся следующим методом. Положим <tex>m = 2^{2^t}</tex>. Начиная с маленьких <tex>m</tex> будем запускать наш алгоритм, причем если на третьем шаге Джарвис уже сделал <tex>m</tex> шагов, то мы выбрали наше <tex>m</tex> слишком маленьким, будем увеличивать, пока не алгоритмстанет <tex>m \ge k</tex>.Тогда общее время алгоритма - <tex> \sum_{t=0}^{O(\log\log k)} O\left(n \log(2^{2^t})\right) = O(n) \sum_{t=0}^{O(\log\log k)} O(2^t) = O\left(n \cdot 2^{1+O(\log\log k)}\right) = O(n \log k).</tex> == Ссылки == * [http://en.wikipedia.org/wiki/Chan%27s_algorithm Английская статья — Wikipedia]* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A7%D0%B0%D0%BD%D0%B0 Русская статья — Wikipedia]
= Алгоритм QuickHull =
