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

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

Описание

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

  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(N^2).

Лемма Решением уравнения (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)

См. также

Ссылки