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

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

Описание

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

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

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

Определения

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

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

Реализация

Пусть мы уже имеем построенные выпуклые оболочки ${\displaystyle P_{1}}$ и ${\displaystyle P_{2}}$.

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

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

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

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

Ссылки

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