Участник:Zhu.a-v/Алгоритм Киркпатрика: различия между версиями
Перейти к навигации
Перейти к поиску
Zhu.a-v (обсуждение | вклад) (Новая страница: «Автор статьи: Журавская Александра =Свойства и структура алгоритма= Алгоритм Киркпатри…») |
Zhu.a-v (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
=Свойства и структура алгоритма= | =Свойства и структура алгоритма= | ||
| + | |||
Алгоритм Киркпатрика решает [[Построение выпуклой оболочки набора точек|задачу построения выпуклой оболочки набора точек]] методом "разделяй и властвуй" <ref>Kirkpatrick, David G.; Seidel, Raimund (1986). "The ultimate planar convex hull algorithm". SIAM Journal on Computing. 15 (1): 287–299.</ref>. | Алгоритм Киркпатрика решает [[Построение выпуклой оболочки набора точек|задачу построения выпуклой оболочки набора точек]] методом "разделяй и властвуй" <ref>Kirkpatrick, David G.; Seidel, Raimund (1986). "The ultimate planar convex hull algorithm". SIAM Journal on Computing. 15 (1): 287–299.</ref>. | ||
| + | |||
==Общее описание алгоритма== | ==Общее описание алгоритма== | ||
| + | |||
Выпуклой оболочкой множества <math> X </math> называется наименьшее выпуклое множество, содержащее множество <math> X </math>. | Выпуклой оболочкой множества <math> X </math> называется наименьшее выпуклое множество, содержащее множество <math> X </math>. | ||
| + | |||
Справедлива следующая интерпретация выпуклой оболочки: если вбить в деревянную доску несколько гвоздей, забивая их только до середины ножки, затем накинуть вокруг них петлю веревки и затянуть, веревка опишет выпуклую оболочку для множества точек-гвоздей. | Справедлива следующая интерпретация выпуклой оболочки: если вбить в деревянную доску несколько гвоздей, забивая их только до середины ножки, затем накинуть вокруг них петлю веревки и затянуть, веревка опишет выпуклую оболочку для множества точек-гвоздей. | ||
| + | |||
Применим рекурсивный подход "разделяй и властвуй" для решения поставленной задачи: | Применим рекурсивный подход "разделяй и властвуй" для решения поставленной задачи: | ||
| + | |||
1. Если множество состоит менее, чем из <math> 6 </math> элементов, найдем выпуклую оболочку перебором наборов точек. Иначе шаг 2. | 1. Если множество состоит менее, чем из <math> 6 </math> элементов, найдем выпуклую оболочку перебором наборов точек. Иначе шаг 2. | ||
| + | |||
2. Проведем на плоскости прямую, разделяющую множество на 2 непустых подмножества. Для каждого подмножества выполним 1. Перейдем на шаг 3. | 2. Проведем на плоскости прямую, разделяющую множество на 2 непустых подмножества. Для каждого подмножества выполним 1. Перейдем на шаг 3. | ||
| + | |||
3. Построим общую выпуклую оболочку по двум, построенным на предыдущем шаге. | 3. Построим общую выпуклую оболочку по двум, построенным на предыдущем шаге. | ||
==Математическое описание алгоритма== | ==Математическое описание алгоритма== | ||
| + | |||
Ясно, что выпуклая оболочка множества точек на плоскости <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>. | Ясно, что выпуклая оболочка множества точек на плоскости <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>. | ||
| Строка 27: | Строка 36: | ||
==Возможные способы и особенности параллельной реализации алгоритма== | ==Возможные способы и особенности параллельной реализации алгоритма== | ||
==Масштабируемость алгоритма и его реализации== | ==Масштабируемость алгоритма и его реализации== | ||
| − | ==Динамические характеристики и эффективность реализации алгоритма | + | ==Динамические характеристики и эффективность реализации алгоритма== |
==Выводы для классов архитектур== | ==Выводы для классов архитектур== | ||
==Существующие реализации алгоритма== | ==Существующие реализации алгоритма== | ||
=Литература= | =Литература= | ||
<references \> | <references \> | ||
Версия 22:31, 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. Если множество состоит менее, чем из [math] 6 [/math] элементов, найдем выпуклую оболочку перебором наборов точек. Иначе шаг 2.
2. Проведем на плоскости прямую, разделяющую множество на 2 непустых подмножества. Для каждого подмножества выполним 1. Перейдем на шаг 3.
3. Построим общую выпуклую оболочку по двум, построенным на предыдущем шаге.
1.2 Математическое описание алгоритма
Ясно, что выпуклая оболочка множества точек на плоскости [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.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 \>
- ↑ Kirkpatrick, David G.; Seidel, Raimund (1986). "The ultimate planar convex hull algorithm". SIAM Journal on Computing. 15 (1): 287–299.
