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

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

Описание

Дано множество $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 2T(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(P_{1}\cup P_{2})$. Все остальные точки упорядочиваем по полярному углу относительно точки $A$, слиянием двух упорядоченных списков вершин за время $O(N_{1})+O(N_{2})=O(N)$, а затем применяем к полученному списку метод обхода Грэхема, требующий лишь линейное время.
   2. Точка $A$ является внутренней точкой многоугольника $P_{2}$. Упорядочиваем вершины обоих многоугольников относительно центра $A$, сливая два упорядоченных списка вершин $P_{1}$ и $P_{2}$ за $O(N)$.
3. Теперь к полученному списку вершин можно применить алгоритм Грэхема за исключением фазы сортировки точек по полярной координате, тогда он будет выполнен за линейное время.

Теперь получена выпуклая оболочка объединения выпуклых многоугольников $P_{1}\cup P_{2}$.

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

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

Ссылки

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