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

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

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

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

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

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

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

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

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

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

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

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

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