Алгоритм Киркпатрика

Построение выпуклой оболочки методом «разделяй и властвуй» — алгоритм построения выпуклой оболочки.

Описание

Дано множество $S$, состоящее из $N$ точек.

1. Если $N \leq N_0$ ($N_0$ — некоторое небольшое целое число), то построить выпуклую оболочку одним из известных методов и остановиться, иначе перейти к шагу 2.
2. Разобьем исходное множество $S$ произвольным образом на два примерно равных по мощности подмножества $S_1$ и $S_2$ (пусть $S_1$ содержит $N/2$ точек, а $S_2$ содержит $N - N/2$ точек).
3. Рекурсивно находим выпуклые оболочки каждого из подмножеств $S_1$ и $S_2$.
4. Строим выпуклую оболочку исходного множества как выпуклую оболочку объединения двух выпуклых многоугольников $CH(S_1)$ и $CH(S_2)$.

Поскольку: $CH(S) = CH(S1 \cup S2) = CH(CH(S_1) \cup CH(S_2))$, сложность этого алгоритма является решением рекурсивного соотношения $T(N) \leq 2 T(N/2) + f(N)$ , где $f(N)$ — время построения выпуклой оболочки объединения двух выпуклых многоугольников, каждый из которых имеет около $N/2$ вершин. Далее будет показано, что $T(N) = O(N \log N)$.

Определения

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

К выпуклому многоугольнику $P$ можно построить опорные прямые из точки $A$, не принадлежащей ему. Воспользуемся тем, что прямая $AP_i$, где $P_i$ — некоторая вершина многоугольника $P$, является опорной к $P$ в том и только в том случае, если ребра $(P_{i-1}, P_i)$ и $(P_i, P_{i+1})$ лежат в одной полуплоскости, ограниченной этой прямой. Нетрудно видеть, что для построения опорных прямых требуется в худшем случае один обход вершин многоугольника $P$, то есть они ищутся за линейное время.

Реализация

Пусть мы уже имеем построенные выпуклые оболочки $P_1$ и $P_2$.

1. Найдём некоторую внутреннюю точку $A$ многоугольника $P_1$ (например, центроид любых трёх вершин $P_1$). Такая точка $A$ будет внутренней точкой $CH(P_1 \cup P_2)$.
2. Возможно два случая:
   1. Точка $A$ не является внутренней точкой многоугольника $P_2$. Проводим две опорные прямые для многоугольника $P_2$, проходящие через точку $A$. Эти опорные прямые проходят через вершины $B$ и $C$ многоугольника $P_2$. Все точки внутри треугольника $ABC$ не принадлежат границе выпуклой оболочки $CH(P1 \cup P2)$. Все остальные точки упорядочиваем по полярному углу относительно точки $A$, слиянием двух упорядоченных списков вершин за время $O(N_1) + O(N_2) = O(N)$, а затем применяем к полученному списку метод обхода Грэхема, требующий лишь линейное время.
   2. Точка $A$ является внутренней точкой многоугольника $P_2$. Упорядочиваем вершины обоих многоугольников относительно центра $A$, сливая два упорядоченных списка вершин $P1$ и $P_2$ за $O(N)$.
3. Теперь к полученному списку вершин можно применить алгоритм Грэхема за исключением фазы сортировки точек по полярной координате, тогда он будет выполнен за линейное время.

Теперь получена выпуклая оболочка объединения выпуклых многоугольников $P_1 \cup P_2$.

Сложность алгоритма

В сумме все три фазы алгоритма выполняются за время $O(N)$. Таким образом, $f(N) = O(N)$ и получаем соотношение $T(N) \leq 2 T(N/2) + O(N)$, решением которого, как известно, является $T(N) = O(N \log N)$, что и определяет сложность алгоритма.

Ссылки

• http://www.cs.umd.edu/~samir/754/kshand.ps (англ.)

Для улучшения этой статьи желательно?: Проставить интервики в рамках проекта Интервики. Проверить достоверность указанной в статье информации. Викифицировать статью.