06.07.2022

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


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

Описание

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

  • Возьмем две крайние точки множества S — левую Л и правую П. Проведем прямую через них. Обозначим через S1 подмножество точек, расположенных выше или на прямой, проходящей через точки Л и П, а через S2 — подмножество точек, расположенных ниже или на той же прямой.
  • Рассмотрим верхнее подмножество S1. Выберем точку Pi, имеющую наибольшее расстояние от прямой ЛП (треугольник ЛPiП имеет наибольшую площадь). Если таких точек несколько, выбираем ту, у которой угол PiЛП наибольший. Точка Pi является вершиной выпуклой оболочки множества. В самом деле, если через точку Pi провести прямую, параллельную прямой ЛП, то выше этой прямой не окажется ни одной точки множества S. Возможно, на построенной прямой окажутся другие точки, но, согласно сделанному выбору, Pi из них самая левая. Т. о. Точка Pi не может быть представлена выпуклой комбинацией двух других точек множества S.Построим прямые ЛPi и PiП. Точки, расположенные справа от обеих прямых, могут быть исключены из дальнейшего рассмотрения, поскольку они являются внутренними точками треугольника ЛPiП, то есть не принадлежат CH(S) — границе выпуклой оболочки.
  • Теперь рассмотрим подмножество точек S11, расположенных слева от прямой ЛPi или на ней, и подмножество точек S12, расположенных слева от прямой PiП или на ней. Для каждого из подмножеств строим выпуклую оболочку. Выпуклая оболочка множества S1 образуется склейкой упорядоченных списков вершин CH(S11) и CH(S12).
  • Решаем задачу для 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)


    Похожие новости:

    Выпуклая функция

    Выпуклая функция
    Выпуклая функция (выпуклая вниз функция) — функция, для которой отрезок между любыми двумя точками её графика в векторном пространстве лежит не ниже соответствующей дуги графика. Эквивалентно:

    Эпсилон-окрестность

    Эпсилон-окрестность
    ε {displaystyle varepsilon } -окрестность множества в функциональном анализе и смежных дисциплинах — это такое множество, каждая точка которого удалена от данного множества

    Конструкция Proj

    Конструкция Proj
    Proj — это конструкция, аналогичная конструкции аффинных схем как спектров колец, с помощью которой строятся схемы, обладающие свойствами проективных пространств и проективных многообразий. В этой

    Алгоритм заметающей прямой

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

    Добавить комментарий!

    Ваше Имя:
    Ваш E-Mail:
    Введите два слова, показанных на изображении: *
    Популярные новости
    Как купить квартиру в новом ЖК в Москве?
    Как купить квартиру в новом ЖК в Москве?
    Купить квартиру в Москве в наше время желают многие люди. Фирма «Forma» – это надежный застройщик в...
    Однорольные монтажные блоки GEARSEN – особенности разных серий
    Однорольные монтажные блоки GEARSEN – особенности разных серий
    Выполнение грузоподъемных и такелажных работ предусматривает необходимость использования...
    Юкам-Груп – эффективное конвейерное и автоматизированное оборудование
    Юкам-Груп – эффективное конвейерное и автоматизированное оборудование
    Каждое предприятие старается повысить эффективность своей деятельности. Для этого можно...
    Все новости