Участник:Zhu.a-v/Алгоритм Киркпатрика: различия между версиями
Zhu.a-v (обсуждение | вклад) |
Zhu.a-v (обсуждение | вклад) |
||
| Строка 11: | Строка 11: | ||
Справедлива следующая интерпретация выпуклой оболочки: если вбить в деревянную доску несколько гвоздей, забивая их только до середины ножки, затем накинуть вокруг них петлю веревки и затянуть, веревка опишет выпуклую оболочку для множества точек-гвоздей. | Справедлива следующая интерпретация выпуклой оболочки: если вбить в деревянную доску несколько гвоздей, забивая их только до середины ножки, затем накинуть вокруг них петлю веревки и затянуть, веревка опишет выпуклую оболочку для множества точек-гвоздей. | ||
| − | + | ==Математическое описание алгоритма== | |
| + | |||
| + | Входные данные: множество точек <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>. Выберем для этого следующую прямую: <math> x = \frac{\sum_{(a,b) \in T} a}{|T|} </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>. <ref>Местецкий Л.М. Лекции по вычислительной геометрии. Учебное пособие. ВМК МГУ, 2013.</ref> | ||
==Вычислительное ядро алгоритма== | ==Вычислительное ядро алгоритма== | ||
Версия 23:34, 23 октября 2017
Автор статьи: Журавская Александра
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритма
Алгоритм Киркпатрика решает задачу построения выпуклой оболочки набора точек методом "разделяй и властвуй" [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]. Выберем для этого следующую прямую: [math] x = \frac{\sum_{(a,b) \in T} a}{|T|} [/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]. [2]
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
1.9 Входные и выходные данные алгоритма
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
3 Литература
<references \>
