Версия от 20:34, 23 октября 2017

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

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

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

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

Выпуклой оболочкой множества [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]. ^[2]

Вычислительное ядро алгоритма

Макроструктура алгоритма

Схема реализации последовательного алгоритма

Последовательная сложность алгоритма

Информационный граф

Ресурс параллелизма алгоритма

Входные и выходные данные алгоритма

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

Программная реализация алгоритма

Особенности реализации последовательного алгоритма

Локальность данных и вычислений

Возможные способы и особенности параллельной реализации алгоритма

Масштабируемость алгоритма и его реализации

Динамические характеристики и эффективность реализации алгоритма

Выводы для классов архитектур

Существующие реализации алгоритма

Литература

↑ Kirkpatrick, David G.; Seidel, Raimund (1986). "The ultimate planar convex hull algorithm". SIAM Journal on Computing. 15 (1): 287–299.
↑ Местецкий Л.М. Лекции по вычислительной геометрии. Учебное пособие. ВМК МГУ, 2013.

[1] Kirkpatrick, David G.; Seidel, Raimund (1986). "The ultimate planar convex hull algorithm". SIAM Journal on Computing. 15 (1): 287–299.

[2] Местецкий Л.М. Лекции по вычислительной геометрии. Учебное пособие. ВМК МГУ, 2013.

[1]

[2]

@@ Строка 11: / Строка 11: @@
 Справедлива следующая интерпретация выпуклой оболочки: если вбить в деревянную доску несколько гвоздей, забивая их только до середины ножки, затем накинуть вокруг них петлю веревки и затянуть, веревка опишет выпуклую оболочку для множества точек-гвоздей.
-Применим рекурсивный подход "разделяй и властвуй" для решения поставленной задачи:
+==Математическое описание алгоритма==
+Входные данные: множество точек <math> X = {(x_1,y_1),(x_2,y_2),...,(x_n,y_n)}</math>.
-. Если множество состоит менее, чем из <math> 6 </math> элементов, вычислим выпуклую оболочку напрямую перебором наборов точек. Иначе шаг 2.
+Ясно, что выпуклая оболочка множества точек на плоскости <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>.
-. Проведем на плоскости прямую, разделяющую множество на 2 примерно одинаковых подмножества. Для каждого из них найдем выпуклую оболочку. Перейдем на шаг 3.
+Выходные данные: множество точек <math> conv X </math> --- вершины выпуклой оболочки для множества <math> X </math>.
-. Построим общую выпуклую оболочку по двум, построенным на предыдущем шаге.
-==Математическое описание алгоритма==
+Применим рекурсивный подход "разделяй и властвуй" для решения поставленной задачи:
-Ясно, что выпуклая оболочка множества точек на плоскости <math> X = {(x_1,y_1),(x_2,y_2),...,(x_n,y_n)}</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>.
+. Если множество состоит из 1 элемента, его выпуклая оболочка совпадает с самим множеством. Иначе шаг 2.
-Для выполнения шага 1 достаточно проверить все возможные тройки, четверки и пятерки точек и выбрать из них подходящую под определение выпуклой оболочки.
+. Проведем на плоскости прямую, разделяющую множество на два примерно одинаковых подмножества <math> X_l </math>, <math> X_r </math>. Выберем для этого следующую прямую: <math> x = \frac{\sum_{(a,b) \in T} a}{|T|} </math> --- это вертикальная линия, медиана абцисс точек множества, для которого на текущем шаге строится выпуклая оболочка. Для каждого из полученных подмножеств найдем выпуклую оболочку. Перейдем на шаг 3.
-Шаг 2 требует выбора разделяющей прямой: выберем прямую <math> x = /underline{x} </math>
+. Построим <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>. <ref>Местецкий Л.М. Лекции по вычислительной геометрии. Учебное пособие. ВМК МГУ, 2013.</ref>
 ==Вычислительное ядро алгоритма==

Участник:Zhu.a-v/Алгоритм Киркпатрика: различия между версиями