Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
При разработке на основе этого метода алгоритма с линейной сложностью в среднем возникает проблема, связанная с шагом разбиения множества на части. Действительно, в том виде, как это сделано в разд. 3.3.5, это разбиение могло бы потребовать линейного времени, как того требует простое копирование подзадач. Такой подход, однако, приводил бы к оценке 0(N\ogN) для полного времени выполнения алгоритма. Таким образом, следует использовать иной подход, чтобы одновременно достичь двух следующих целей:
(1) шаг разбиения должен выполняться за время 0(№), где р < 1;
(2) точки в каждом из двух подмножеств должны подчиняться тому же закону распределения, что и исходное множество точек.
Вторая цель может быть довольно легко достигнута, если вначале выполнить произвольную перестановку исходных точек и расположить их в массиве (это делается путем записи точек в этот массив в порядке их поступления). Тем самым гарантируется, что любая подпоследовательность полученной последовательности является случайной, т. е. она подчиняется закону исходного распределения. Каждая подзадача касается множества точек, представленных некоторой последовательностью элементов массива (подмассивом), и это множество полностью определяется двумя указателями на граничные элементы соответствующего подмассива. Так что разбиение осуществляется путем расщепления подмассива в средней его части (эта операция выполняется за постоянное время) с последующей передачей в каждом из рекурсивных обращений к процедуре лишь
4.1. Расширения и варианты
187
двух указателей. Использование такого приема позволяет достичь первой цели. Эта цель неявно достигается, если воспользоваться итерационной (а не рекурсивной) схемой реализации алгоритма. При такой реализации последовательно обрабатывались бы снизу вверх сначала множества из четырех точек, затем из восьми и т. д.
Таким образом, время выполнения шага слияния пропорционально сумме размеров выпуклых оболочек каждого из двух подмножеств. Обозначим последнюю величину C(N) и, как обычно, T(N) —время работы алгоритма на множестве размера N. Без труда получаем следующее рекуррентное соотношение:
T(N)^2T(N/2) + C(N). Если теперь положить Тср (N) Д Е [Т (N)] (оператор Е[ ] обозначает математическое ожидание), то, учитывая линейность оператора Е, получаем новое рекуррентное соотношение:
Гср(ЛО<27-ср(ВД + ?[С(ЛО]. (4-5)
Решение этого соотношения зависит от вида E[C(N)]. В частности, если
fO(N), то Tcp(N) = 0 (N log N),
E[C(N)] = )o(N/logN), то TCP(N) = О (N log log N), (4.6) [o(Np),p<l, то Гср(Л0 = О(Л0.
Благодаря линейности оператора Е[ ] значение E[C(N)] не превосходит удвоенного значения математического ожидания размером h(N/2) выпуклой оболочки множества из N/2 точек. Учитывая, что для всех упоминавшихся выше распределений имеет место свойство E[h(N/2)] = 0((JV/2)P) для некоторого р < 1, то E[C(N)] = 0(NP). Полученный результат можно сформулировать в следующей теореме:
Теорема 4.5. Для Np-распределения выпуклая оболочка выборки из N точек на плоскости может быть найдена в среднем за время O(N).
Довольно соблазнительно сказать, что проведенный анализ применим и к описанному в разд. 3.4.3 алгоритму Препараты и Хонга построения выпуклой оболочки в трехмерном пространстве, который также основывается на методе «разделяй и властвуй». Однако (по крайней мере в приведенном изложении) этот алгоритм существенным образом использует факт разделимости двух выпуклых оболочек при их слиянии. К сожалению, это предположение нарушает условие, согласно которому в ходе обработки каждое подмножество должно быть случайным и подчиняться одному и тому же распределению.
Гл. 4. Выпуклые оболочки: расширения и приложения
4.1.2. Алгоритмы аппроксимации выпуклой оболочки
Вместо выбора алгоритма построения выпуклой оболочки на основании его сложности в среднем (о чем говорилось в предыдущем разделе) можно пойти по альтернативному пути, разрабатывая алгоритмы, строящие аппроксимации для реальной выпуклой оболочки, разменивая тем самым точность на
(с)
Рис. 4.1. Иллюстрация алгоритма аппроксимации выпуклой оболочки: (а) — задано множество точек на плоскости, в котором выделяются самые левые и самые правые точки; (Ь) — разбиение множества точек на части в зависимости от принадлежности их одной из k полос и определение в каждой полосе точек с экстремальной ординатой; (с)—приближенная выпуклая оболочка.
простоту и эффективность алгоритма. Такой алгоритм мог бы, в частности, быть очень полезным для приложений, когда необходимо быстро получить решение, жертвуя ради этого даже точностью. Так, например, это вполне приемлемо в прикладной статистике, где результаты наблюдений не являются точными, а известны с некоторой вполне определенной точностью.
Здесь будет рассмотрен один из таких алгоритмов для плоского случая [Bentley, Faust, Preparata (1982)]. Основная идея этого алгоритма проста и состоит в том, чтобы выделить из множества точек некоторое подмножество, выпуклая оболочка которого и будет служить аппроксимацией выпуклой оболочки исходного множества точек. Однако конкретная схема выделения аппроксимирующего подмножества точек, которая будет выбрана далее, основывается на модели вычислений, отличной
