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

Zhu.a-v: /* Свойства и структура алгоритма */

2017-10-23T20:40:33Z

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

← Предыдущая версия		Версия от 20:40, 23 октября 2017
Строка 2:		Строка 2:

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

	Алгоритм Киркпатрика решает [[Построение выпуклой оболочки набора точек\|задачу построения выпуклой оболочки набора точек]] методом "разделяй и властвуй" <ref>Kirkpatrick, David G.; Seidel, Raimund (1986). "The ultimate planar convex hull algorithm". SIAM Journal on Computing. 15 (1): 287–299.</ref>.

	==Общее описание алгоритма==		==Общее описание алгоритма==
Строка 10:		Строка 8:

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

			Алгоритм Киркпатрика решает [[Построение выпуклой оболочки набора точек\|задачу построения выпуклой оболочки набора точек]] методом "разделяй и властвуй" <ref>Kirkpatrick, David G.; Seidel, Raimund (1986). "The ultimate planar convex hull algorithm". SIAM Journal on Computing. 15 (1): 287–299.</ref>. Для этого множество разделяется некоторой прямой на два подмножества, для этих подмножеств рекурсивно запускается алгоритм поиска выпуклой оболочки, затем полученные выпуклые оболочки специальным образом "сшивают" в одну общую выпуклую оболочку.


	==Математическое описание алгоритма==		==Математическое описание алгоритма==
Строка 41:		Строка 42:
	==Входные и выходные данные алгоритма==		==Входные и выходные данные алгоритма==
	==Свойства алгоритма==		==Свойства алгоритма==

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

Zhu.a-v в 20:37, 23 октября 2017

2017-10-23T20:37:51Z

← Предыдущая версия		Версия от 20:37, 23 октября 2017
Строка 15:		Строка 15:
	Входные данные: множество точек <math> X = {(x_1,y_1),(x_2,y_2),...,(x_n,y_n)}</math>.		Входные данные: множество точек <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> 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>.		Выходные данные: множество точек <math> conv(X) </math> --- вершины выпуклой оболочки для множества <math> X </math>.


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

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

Zhu.a-v в 20:34, 23 октября 2017

2017-10-23T20:34:13Z

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

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

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

	1. ~~Если множество состоит менее~~, ~~чем из~~ <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. Проведем на плоскости прямую, разделяющую~~ множество ~~на 2 примерно одинаковых подмножества. Для каждого из них найдем выпуклую оболочку. Перейдем на шаг 3~~.		Выходные данные: множество точек <math> conv X </math> --- вершины выпуклой оболочки для множества <math> X </math>.

	~~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>~~.		1. Если множество состоит из 1 элемента, его выпуклая оболочка совпадает с самим множеством. Иначе шаг 2.

	~~Для выполнения шага 1 достаточно проверить все возможные тройки~~, ~~четверки и пятерки~~ точек ~~и выбрать~~ из ~~них подходящую под определение выпуклой оболочки~~.		2. Проведем на плоскости прямую, разделяющую множество на два примерно одинаковых подмножества <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>		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>

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

Zhu.a-v в 19:48, 23 октября 2017

2017-10-23T19:48:02Z

← Предыдущая версия		Версия от 19:48, 23 октября 2017
Строка 13:		Строка 13:
	Применим рекурсивный подход "разделяй и властвуй" для решения поставленной задачи:		Применим рекурсивный подход "разделяй и властвуй" для решения поставленной задачи:

	1. Если множество состоит менее, чем из <math> 6 </math> элементов, ~~найдем~~ выпуклую оболочку перебором наборов точек. Иначе шаг 2.		1. Если множество состоит менее, чем из <math> 6 </math> элементов, вычислим выпуклую оболочку напрямую перебором наборов точек. Иначе шаг 2.

	2. Проведем на плоскости прямую, разделяющую множество на 2 ~~непустых~~ подмножества. Для каждого ~~подмножества выполним 1~~. Перейдем на шаг 3.		2. Проведем на плоскости прямую, разделяющую множество на 2 примерно одинаковых подмножества. Для каждого из них найдем выпуклую оболочку. Перейдем на шаг 3.

	3. Построим общую выпуклую оболочку по двум, построенным на предыдущем шаге.		3. Построим общую выпуклую оболочку по двум, построенным на предыдущем шаге.
Строка 21:		Строка 21:
	==Математическое описание алгоритма==		==Математическое описание алгоритма==

	Ясно, что выпуклая оболочка множества точек на плоскости <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>.

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

			Шаг 2 требует выбора разделяющей прямой: выберем прямую <math> x = /underline{x} </math>


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

Zhu.a-v в 19:31, 23 октября 2017

2017-10-23T19:31:49Z

Zhu.a-v: Новая страница: «Автор статьи: Журавская Александра =Свойства и структура алгоритма= Алгоритм Киркпатри…»

2017-10-23T19:28:18Z

Новая страница: «Автор статьи: Журавская Александра =Свойства и структура алгоритма= Алгоритм Киркпатри…»

Новая страница

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

=Свойства и структура алгоритма=
Алгоритм Киркпатрика решает [[Построение выпуклой оболочки набора точек|задачу построения выпуклой оболочки набора точек]] методом "разделяй и властвуй" <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>.
Справедлива следующая интерпретация выпуклой оболочки: если вбить в деревянную доску несколько гвоздей, забивая их только до середины ножки, затем накинуть вокруг них петлю веревки и затянуть, веревка опишет выпуклую оболочку для множества точек-гвоздей.
Применим рекурсивный подход "разделяй и властвуй" для решения поставленной задачи:
1. Если множество состоит менее, чем из <math> 6 </math> элементов, найдем выпуклую оболочку перебором наборов точек. Иначе шаг 2.
2. Проведем на плоскости прямую, разделяющую множество на 2 непустых подмножества. Для каждого подмножества выполним 1. Перейдем на шаг 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>.

==Вычислительное ядро алгоритма==
==Макроструктура алгоритма==
==Схема реализации последовательного алгоритма==
==Последовательная сложность алгоритма==
==Информационный граф==
==Ресурс параллелизма алгоритма==
==Входные и выходные данные алгоритма==
==Свойства алгоритма==
=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==
==Масштабируемость алгоритма и его реализации==
==Динамические характеристики и эффективность реализации алгоритма
==Выводы для классов архитектур==
==Существующие реализации алгоритма==
=Литература=
<references \>

← Предыдущая версия		Версия от 19:31, 23 октября 2017
Строка 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 \>