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

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

Описание

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

1. Если ( — некоторое небольшое целое число), то построить выпуклую оболочку одним из известных методов и остановиться, иначе перейти к шагу 2.
2. Разобьем исходное множество произвольным образом на два примерно равных по мощности подмножества и (пусть содержит точек, а содержит точек).
3. Рекурсивно находим выпуклые оболочки каждого из подмножеств и .
4. Строим выпуклую оболочку исходного множества как выпуклую оболочку объединения двух выпуклых многоугольников и .

Поскольку: , сложность этого алгоритма является решением рекурсивного соотношения , где  — время построения выпуклой оболочки объединения двух выпуклых многоугольников, каждый из которых имеет около вершин. Далее будет показано, что .

Определения

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

К выпуклому многоугольнику можно построить опорные прямые из точки , не принадлежащей ему. Воспользуемся тем, что прямая , где  — некоторая вершина многоугольника , является опорной к в том и только в том случае, если ребра и лежат в одной полуплоскости, ограниченной этой прямой. Нетрудно видеть, что для построения опорных прямых требуется в худшем случае один обход вершин многоугольника , то есть они ищутся за линейное время.

Реализация

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

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

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

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

В сумме все три фазы алгоритма выполняются за время . Таким образом, и получаем соотношение , решением которого, как известно, является , что и определяет сложность алгоритма.

Ссылки

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