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

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

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

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

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

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

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

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

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

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

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

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

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

2. Проведем на плоскости прямую, разделяющую множество на два примерно одинаковых подмножества [math] X_l [/math], [math] X_r [/math]. Выберем для этого вертикальную линию, являющуюся медианой абцисс точек множества, для которого на текущем шаге строится выпуклая оболочка. Для каждого из полученных подмножеств найдем выпуклую оболочку. Перейдем на шаг 3.

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

3 Литература

<references \>