Участник:Zhu.a-v/Алгоритм Киркпатрика

Автор статьи: Журавская Александра

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

Алгоритм Киркпатрика решает задачу построения выпуклой оболочки набора точек методом "разделяй и властвуй" .

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

Выпуклой оболочкой множества [math]\displaystyle{ X }[/math] называется наименьшее выпуклое множество, содержащее множество [math]\displaystyle{ X }[/math].

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

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

Входные данные: множество точек [math]\displaystyle{ X = {(x_1,y_1),(x_2,y_2),...,(x_n,y_n)} }[/math].

Ясно, что выпуклая оболочка множества точек на плоскости [math]\displaystyle{ X }[/math] --- это выпуклый многоугольник, вершины которого содержатся в [math]\displaystyle{ X }[/math], и все остальные элементы [math]\displaystyle{ X }[/math] лежат внутри этого многоугольника. Значит, задача поиска выпуклой оболочки [math]\displaystyle{ conv X }[/math] сводится к выбору такого набора вершин [math]\displaystyle{ (x_{i_1},y_{i_1}),(x_{i_2},y_{i_2}),...,(x_{i_n},y_{i_n}) }[/math] , которые образуют выпуклый многоугольник, содержащий все точки множества [math]\displaystyle{ X }[/math].

Выходные данные: множество точек [math]\displaystyle{ conv X }[/math] --- вершины выпуклой оболочки для множества [math]\displaystyle{ X }[/math].

Применим рекурсивный подход "разделяй и властвуй" для решения поставленной задачи:

1. Если множество состоит из 1 элемента, его выпуклая оболочка совпадает с самим множеством. Иначе шаг 2.

2. Проведем на плоскости прямую, разделяющую множество на два примерно одинаковых подмножества [math]\displaystyle{ X_l }[/math], [math]\displaystyle{ X_r }[/math]. Выберем для этого следующую прямую: [math]\displaystyle{ x = \frac{\sum_{(a,b) \in T} a}{|T|} }[/math] --- это вертикальная линия, медиана абцисс точек множества, для которого на текущем шаге строится выпуклая оболочка. Для каждого из полученных подмножеств найдем выпуклую оболочку. Перейдем на шаг 3.

3. Построим [math]\displaystyle{ conv(X) }[/math] по [math]\displaystyle{ conv(X_l) }[/math] и [math]\displaystyle{ conv(X_r) }[/math], построенным на предыдущем шаге. Поскольку множества [math]\displaystyle{ X_l }[/math] и [math]\displaystyle{ X_r }[/math] разделены вертикальной линией, их выпуклые оболочки представляют собой непересекающиеся выпуклые многоугольники. Следовательно, для построения общей выпуклой оболочки этих многоугольников достаточно найти их общие касательные - верхнюю и нижнюю, а затем отбросить правую цепочку в многоугольнике [math]\displaystyle{ conv(X_l) }[/math] и левую цепочку в многоугольнике [math]\displaystyle{ conv(X_r) }[/math]. Пусть левый и правый многоугольники представлены списками вершин [math]\displaystyle{ P_l }[/math] и [math]\displaystyle{ P_r }[/math]. Поиск общей касательной начнем с мостика [math]\displaystyle{ (u,v) }[/math], соединяющего самую правую вершину [math]\displaystyle{ u }[/math] в [math]\displaystyle{ P_l }[/math] с самой левой вершиной [math]\displaystyle{ v }[/math] в [math]\displaystyle{ P_r }[/math]. Далее будем последовательно перемещать эти вершины вдоль границ выпуклых многоугольников против часовой стрелки в [math]\displaystyle{ P_l }[/math] и по часовой стрелке в [math]\displaystyle{ P_r }[/math] до тех пор, пока существуют вершины, лежащие слева от вектора [math]\displaystyle{ (u,v) }[/math]. Таким образом мы найдем общую верхнюю касательную. Аналогично, вычислим нижнюю касательную. Но перемещение теперь осуществляется по часовой стрелке в [math]\displaystyle{ P_l }[/math] и против часовой стрелки в [math]\displaystyle{ P_r }[/math]. Поиск нижней касательной завершается, когда мостик окажется в положении, при котором не существует вершин, лежащих справа от вектора [math]\displaystyle{ (u,v) }[/math].

Литература

<references \>