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

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

Описание

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

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

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

Определения

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

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

Реализация

Пусть мы уже имеем построенные выпуклые оболочки [math]\displaystyle{ P_1 }[/math] и [math]\displaystyle{ P_2 }[/math].

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

Теперь получена выпуклая оболочка объединения выпуклых многоугольников [math]\displaystyle{ P_1 \cup P_2 }[/math].

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

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

Ссылки

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