Алгоритм быстрой оболочки

Алгоритм быстрой оболочки — алгоритм построения выпуклой оболочки. Использует идею быстрой сортировки Хоара

Описание

Множество точек разбивается на два подмножества, каждое из которых будет содержать одну из ломаных, соединение которых дает многоугольник выпуклой оболочки.

1. Возьмем две крайние точки множества S — левую Л и правую П. Проведем прямую через них. Обозначим через S1 подмножество точек, расположенных выше или на прямой, проходящей через точки Л и П, а через S2 — подмножество точек, расположенных ниже или на той же прямой.
2. Рассмотрим верхнее подмножество S1. Выберем точку Pi, имеющую наибольшее расстояние от прямой ЛП (треугольник ЛPiП имеет наибольшую площадь). . Если таких точек несколько, выбираем ту, у которой угол PiЛП наибольший. Точка Pi является вершиной выпуклой оболочки множества. В самом деле, если через точку Pi провести прямую, параллельную прямой ЛП, то выше этой прямой не окажется ни одной точки множества S. Возможно, на построенной прямой окажутся другие точки, но, согласно сделанному выбору, Pi из них самая левая. Т. о. Точка Pi не может быть представлена выпуклой комбинацией двух других точек множества S.Построим прямые ЛPi и PiП. Точки, расположенные справа от обеих прямых, могут быть исключены из дальнейшего рассмотрения, поскольку они являются внутренними точками треугольника ЛPiП, то есть не принадлежат CH(S) — границе выпуклой оболочки.
3. Теперь рассмотрим подмножество точек S11, расположенных слева от прямой ЛPi или на ней, и подмножество точек S12, расположенных слева от прямой PiП или на ней. Для каждого из подмножеств строим выпуклую оболочку. Выпуклая оболочка множества S1 образуется склейкой упорядоченных списков вершин CH(S11) и CH(S12).
4. Решаем задачу для S2.

Сложность алгоритма

Сложность алгоритма состоит из сложности построения двух подмножеств рассматриваемого множества O(N) и сложностей решения подзадач для каждого из подмножеств: T(N) = T(a) + T(b) + O(N).

В лучшем случае, когда задача разбивается на две равномощные подзадачи, сложность алгоритма является решением рекурсивного уравнения:

(1) T(N) = 2 T(N/2) + O(N) =>

(2) T(N) = O(N log N).

В худшем случае:

(3) T(N) = T(1) + T(N 1) + O(N) =>

(4) T(N) = O(N2).

Лемма Решением уравнения (1) является функция (2) Пусть N = 2k. Тогда T(2k) = 2 T(2k 1) + C 2k ; T(2k 1) = 2 T(2k 2) + C 2k 1 => T(2k) = 4 T(2k 2) + 2 °C 2k 1 + С 2k = 4 T(2k 2) + 2 °C 2k => T(2k) = 2m T(2k m) + m С 2k При m = k (= logN) алгоритм заканчивает работу: T(N) = N T(1) + C logN N = O(N logN)

См. также

• Алгоритм Грэхема
• Алгоритм Джарвиса
• Алгоритм Чана

Ссылки

• Реализация на c++
• [1] (англ.)(недоступная ссылка)

Для улучшения этой статьи желательно?: Проставить интервики в рамках проекта Интервики. Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Переработать оформление в соответствии с правилами написания статей. Викифицировать статью.