91
правка
Изменения
→Последовательный алгоритм
|definition = Нам дано два выпуклых многоугольника A и B, которые были разрезаны отрезком X, и взята верхняя часть. Нужно провести такую касательную через 2 точки многоугольника, что все точки находятся либо на касательной либо ниже.
}}
[[Файл:Parallel-convex-hull-tangent-tangent.png|300px|thumb|right|Касательные из каждой точки]]
Давайте мысленно проведем касательные из каждой точки A на многоугольник B. Только одна из них является истинной. Здесь будет работать примерно такая же стратегия, что и в прошлом. Если мы понимаем с помощью предиката левого поворота, что касательная выше, то правильная точка находится до нашей, иначе дальше нашей. Снова сделаем бинпоиск. Только на сей раз проверка на то, что точка находится левее/правее нужной будет требовать от нас <tex>O(log(n))</tex>. Таким образом, алгоритм нахождения общей касательной будет работать за <tex>O(log^2(n))</tex>.
Теперь мы можем соединять две выпуклые оболочки в одну просто проводя касательную между ними и выпиливая у первого многоугольника все, что дальше точки касания, а у второго многоугольника все, что находится до точки касания за <tex>O(n)<\tex>. Задача решена.
==Параллельный алгоритм==
