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

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

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

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

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

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

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

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

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

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

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

3 Литература

<references \>