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

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

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

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

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

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

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

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

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

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

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

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

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

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