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


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

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

Содержание

Описание

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

  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)

См. также

Ссылки



Wikimedia Foundation. 2010.

Смотреть что такое "Алгоритм быстрой оболочки" в других словарях:

  • Алгоритм Грэхема — Алгоритм Грэхема  алгоритм построения выпуклой оболочки в двумерном пространстве. В этом алгоритме задача о выпуклой оболочке решается с помощью стека, сформированного из точек кандидатов. Все точки входного множества заносятся в стек, а… …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

  • Вычислительная геометрия — раздел дискретной математики, в котором рассматриваются алгоритмы для решения геометрических задач. В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного объекта другому, поиск их… …   Википедия

  • Компьютерная геометрия — Вычислительная геометрия раздел дискретной математики, в котором рассматриваются алгоритмы для решения геометрических задач. В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного… …   Википедия

  • Выпуклая оболочка — Выпуклой оболочкой множества называется наименьшее выпуклое множество, содержащее . «Наименьшее множество» здесь означает наименьший элемент по отношению к вложению множеств, то есть такое выпуклое множество, содержащее данную фигуру, что оно… …   Википедия

  • Windows XP — Windows XP …   Википедия

  • Экономическая информационная система — (ЭИС) представляет собой совокупность организационных, технических, программных и информационных средств, объединённых в единую систему с целью сбора, хранения, обработки и выдачи необходимой информации, предназначенной для выполнения функций… …   Википедия

  • ЭИС — Экономическая информационная система (ЭИС) представляет собой совокупность организационных, технических, программных и информационных средств, объединенных в единую систему с целью сбора, хранения, обработки и выдачи необходимой информации,… …   Википедия