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

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

Дано множество ${\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 (англ.)

У этой статьи есть несколько проблем, помогите их исправить: Достоверность этой статьи поставлена под сомнение. Необходимо проверить точность фактов и достоверность сведений, изложенных в этой статье. Соответствующую дискуссию можно найти на странице обсуждения. (2 июня 2010) Эту статью необходимо исправить в соответствии с правилами Википедии об оформлении статей. Пожалуйста, помогите улучшить эту статью. (2 июня 2010) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.