Алгоритм построения выпуклой оболочки (Киркпатрика – Сайделя).

9

Оригинал см. в гл. 6 в файле geo.pdf

Построение выпуклой оболочки конечного множества точек (особенно в случае точек на плоскости) довольно широко и глубоко исследовано и имеет целый ряд геометрических приложений. Известно, что нижняя оценка нахождения упорядоченной границы выпуклой оболочки n точек на плоскости составляет , и существуют алгоритмы ее построения за время при памяти с использованием только арифметических операций. Известен алгоритм, интересный с точки зрения его быстродействия (статья D.G.Kirpatrick & R.Seidel “The ultimate planar convex hull algorithm” (SIAM Journal on Computing, 15(2) 1986)). Его сложность составляет , а значит, он асимптотически оптимален. Ниже приводится перевод фрагмента упомянутой статьи:

Отсечение и поиск - техника, используемая для отыскания медианы по Блуму, Флойду, Пратту и Тарьяну. Техника, примененная к поиску медианы, выделяет постоянную долю чисел на каждой итерации цикла. Решение рекуррентного уравнения дает нам время алгоритма поиска медианы.

При поиске медианы в списке, мы сначала обобщим проблему.

Мы обсудим проблему поиска минимальных чисел из списка , состоящего из чисел. Сначала мы разделим чисел на групп, каждая по 5 элементов, будем искать медиану в каждой из групп. Пусть будет списком из медиан. Рекурсивно ищем медиану из списка . Можно доказать, что больше или равно хотя бы четверти чисел в исходном списке и меньше либо равно хотя бы четверти чисел в исходном списке .

Следовательно, число разделяет список на 2 подсписка и , такие, что все числа в меньше или равны и все числа в больше или равны . Кроме этого, размер каждого из этих двух подсписков минимально составляет от начального списка. Теперь, если подсписок включает более чисел, рекурсивно вызывается алгоритм поиска минимальных чисел в списке . С другой стороны, если подсписок включает чисел, таких что , рекурсивно вызывается алгоритм поиска минимальных чисел в подсписке . В любом случае, из всей величины списка мы обрабатываем максимум от начального списка . Детали обсуждения алгоритма здесь опускаются. Проведем анализ выше описанного алгоритма поиска медианы.

Допустим, что временная сложность алгоритма от входных данных размера есть . Тогда поиск медианы из списка, который состоит из медиан, потребует время . После для обоих спискови, максимальный размер которых составляет , поиск минимальных чисел в спискеили поиск минимальных чисел в списке потребует время максимально равное . Также понятно, что остальной расчет может быть сделан за время , где . Следовательно, функция удовлетворяет следующему соотношению:

Имеется- целое, т.ч. и ,из чего несложно удостовериться по индукции в том, что

Таким образом.

Неформально основная идея алгоритма поиска и отсечения может быть описана следующим образом:

Алгоритм отсечения и поиска

Входные данные: Задача размера

Выходные данные: Решение этой задачи

НАЧАЛО

0. Если размер задачи – небольшой, непосредственно решаем и останавливаемся.

1. Разделение задачи на небольших задач, размера таким образом, что .

Здесь - фиксированная константа.

0. Рекурсивное решение задач .

1. После обработки результатов выполнения Шага 2 получаем решение задачи.

КОНЕЦ

Допустим, что временная сложность алгоритма Отсечения и Поиска составляет и что Шаг1 и Шаг3 алгоритма потребуют время . Тогда функция может быть представлена как следующее соотношение:

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

Алгоритм построения выпуклой оболочки

(Киркпатрика – Сайделя).

Представим алгоритм Отсечения и Поиска для построения выпуклой оболочки, которым обязаны Киркпатрику и Сайделю. Рассмотрим сначала следующую задачу: