Участник:Aleksey Dumbay/QuickHull

Алгоритм: QuickHull для двумерного случая

Автор статьи: Думбай А.Д. группа 317

Свойства и структура алгоритма

Общее описание алгоритма

Построение выпуклой оболочки множества точек - задача построения минимального по вложенности выпуклого множества, содержащего все точки из исходного множества. В случае конечного числа точек на плоскости выпуклая оболочка описывается некоторым подмножеством точек, которые принадлежат этой выпуклой оболочке. В этом случае выпуклая оболочка представляет собой выпуклый многоугольник с вершинами из этого подмножества точек.

Алгоритм QuickHull - алгоритм построения выпуклой оболочки множества точек в среднем за [math]\displaystyle{ \Theta(N*\log{N}) }[/math] и за [math]\displaystyle{ O(N^2) }[/math] в худшем случае, где [math]\displaystyle{ N }[/math] - мощность множества точек. Алгоритм использует подход, аналогичный подходу QuickSort, разделяя исходное множество на некоторые подмножества, отсекая ненужные точки, после этого применяется рекурсивно к образовавшимся подмножествам, а потом объединяет их. В рамках этого алгоритма решаются две задачи - выделения подмножеств и объединения нескольких выпуклых оболочек вместе.

Есть несколько различных вариантов данного алгоритма, которые по-разному находят подмножества для рекурсивного обхода. Общая их идея заключается в выделении крайних точек и отсечении всех точек, что попали в образованный ими многоугольник. Остальные точки делятся на множества и обрабатываются рекурсивно. Так же существует вариант алгоритма, в котором рекурсивно находится наиболее удаленная от отрезка вершина, отсекается образованный треугольник, а к новым сторонам и разбившемуся множеству алгоритм применяется рекурсивно.

На вход алгоритму подается множество точек на плоскости, на выходе - те точки, которые являются вершинами выпуклой оболочки.

Математическое описание алгоритма

Выпуклое множество [math]\displaystyle{ A }[/math] для векторного пространства [math]\displaystyle{ \mathbb{V} }[/math] над [math]\displaystyle{ \mathbb{R} }[/math] - такое множество, что

[math]\displaystyle{ \forall \textbf{x}, \textbf{y} \in A, \forall \alpha \in [0,1]: \textbf{x} \cdot \alpha + \textbf{y} \cdot (1 - \alpha) \in A }[/math].

Выпуклая оболочка множества точек [math]\displaystyle{ \mathbb{X} }[/math] - это такое выпуклое множество, которое содержит все точки из множества [math]\displaystyle{ \mathbb{X} }[/math] и при этом является минимальным по вложению. В случае [math]\displaystyle{ \mathbb{X} }[/math] из [math]\displaystyle{ \mathbb{R}^2 }[/math] выпуклая оболочка является многоугольником.

На вход алгоритму подается множество [math]\displaystyle{ \mathbb{X} }[/math] из [math]\displaystyle{ \mathbb{R}^2 }[/math], которое описывает набор точек на плоскости, где каждая точка - вектор [math]\displaystyle{ (x,y) }[/math] где компоненты соответствуют координатам на плоскости в декартовой системе координат. [math]\displaystyle{ \mathbb{X} = \{a_1, a_2, \ldots, a_N\} }[/math]. Алгоритм работает в среднем за [math]\displaystyle{ \Theta(N*\log{N}) }[/math] и за [math]\displaystyle{ O(N^2) }[/math] в худшем случае.

Алгоритм строит упорядоченный набор из точек [math]\displaystyle{ x_{1}, x_{2}, \ldots, x_m }[/math], которые образуют многоугольник [math]\displaystyle{ X_1X_2X_3\ldots X_m }[/math], являющийся выпуклой оболочкой множества точек [math]\displaystyle{ \mathbb{X} }[/math], где [math]\displaystyle{ x_i \in A }[/math].