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

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

Описание

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

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

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

Определения

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

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

Реализация

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

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

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

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

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

Ссылки

  • (англ.)
Источник —

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