Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Выпуклые оболочки / report про алг Чена

.pdf
Скачиваний:
40
Добавлен:
01.05.2014
Размер:
336.72 Кб
Скачать

1

1.1. Алгоритм Чена

Если обратить внимание на сложность алгоритма Джарвиса (O(nh)), то можно заметить, что он не является оптимальным в худшем случае, но при небольшом числе крайних точек выпуклой оболочки он будет работать быстрее чем, например, алгоритм Грэхема. Это происходит потому, что сложность алгоритма Джарвиса зависит не только от числа точек в исходном множестве (n), но и от числа вершин выпуклой оболочки (h).

Долгое время одной из центральных была идея создания алгоритма, который был бы оптимальным в худшем случае, но при этом всегда бы был асимптотически не хуже, чем алгоритм Джарвиса. Такой алгоритм со сложностью O(n log h) был предложен Киркпатриком и Сайделем в 1986 году. Его идея достаточно сложна и опирается на возможность нахождения медианы последовательности чисел за линейное в худшем случае время.

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

Пусть дано исходное множество точек P , для которого искомой является его выпуклая оболочка CH(P ). Предположим, что зафиксирован некоторый целочисленный параметр 1 · m · n.

1.Разделим множество P на dmn e непересекающихся подмножеств Pi так, чтобы в каждом подмножестве было не более чем m точек. Очевидно, что такое разбиение всегда осуществимо.

2.Построим выпуклые оболочки CH(Pi) для множеств Pi любым из оптимальных в худшем случае алгоритмов (например, алгоритмом Грэхема).

3.Найдем точку pstart 2 P , которая будет гарантированно включена в выпуклую оболочку CH(P ).

4.Будем выполнять шаги, находя каждый раз такую точку, которая является следующей вершиной выпуклой оболочки в порядке обхода против часовой стрелки. Когда очередная найденная точка p совпадет с pstart будем считать, что алгоритм построил выпуклую оболочку CH(P ).

Для нахождения следующей вершины выпуклой оболочки будет использоваться информация об уже построенных выпуклых оболочках CH(Pi). Базовой операцией будем считать нахождение правой опорной точки выпуклого многоугольника S относительно текущей точки p. Правая опорная точка выпуклого многоугольника S относительно точки p это такая точка q 2 S, что любая точка многоугольника S лежит по левую сторону от ориентированного отрезка [p; q] или на нем.

q

q

p

S

S

 

p

a)

!)

Рис. 1.1. Точка q правая опорная точка многоугольника S относительно точки p. Пример (а) и вырожденный случай, когда точка p принадлежит границе многоугольника (б).

На каждом шаге необходимо найти все правые опорные точки qi выпуклых многоугольников CH(Pi) относительно точки p и линейным поиском выбрать среди них такую точку r, чтобы любая точка qi лежала по левую сторону от ориентированного отрезка [p; r] или на нем. Точка r будет следующей вершиной выпуклой оболочки в порядке обхода против часовой стрелки.

2

algorithm Chan-March-With-Param(P; m)! CH(P )

Вход. Исходное множество точек P = fpi j pi = (xi; yi); i 2 [1::n]g, целочисленный параметр m (1 · m · n). Выход. Выпуклая оболочка множества точек CH(P ), заданная последовательностью вершин (перечисленных в порядке обхода против часовой стрелки).

1Инициализирировать выпуклую оболочку пустой последовательностью точек

2 Разделить множество P на dmn e непересекающихся подмножеств Pi так, чтобы в каждом подмножестве было не более чем m точек

3 Построить выпуклые оболочки CH(Pi) для множеств Pi любым из оптимальных в худшем случае алгоритмов (например, алгоритмом Грэхема)

4Выбрать точку pstart, которая будет являться крайней точкой выпуклой оболочки

p à pstart

 

do

 

AddVertex(p)

 

for 8i 2 [1::d

n

e] do

 

m

5

Найти правую опорную точку qi выпуклого многоугольника CH(Pi) относительно точки p

 

end-do

 

r à q1

 

for 8i 2 [2::d

n

e] do

 

m

 

if (Area(p; qi; r) > 0) or ((Area(p; qi; r) = 0) and (Length(p; r) < Length(p; qi))) then

r à qi end-if

end-do p à r

while p 6= pstart

6Вернуть в качестве результата CH(P )

Правую опорную точку выпуклого многоугольника S относительно точки p можно найти двоичным поиском за время O(log m), где m количество вершин в многоугольнике. Но можно улучшить эту асимптотику, если заметить, что на каждом следующем шаге, правая опорная точка qi либо останется такой же, либо примет значение одной из следующих вершин CH(Pi) в сторону обхода против часовой стрелки, причем никакая вершина не может быть пройдена больше чем два раза. Таким образом, каждый раз, когда нужно найти правую опорную точку qi относительно новой точки p, берется старое значение qi и проверяется следующая за qi точка Next(qi): если оказывается, что точка qi лежит левее ориентированного отрезка [p;Next(qi)] или строго на нем, то в качестве qi берется Next(qi) и операция повторяется, в противном случае опорной точкой считается точка qi. До нахождения правых опорных точек на первом шаге, qi предварительно инициализируются любыми из вершин соответствующих многоугольников CH(Pi).

NEXT(qi)

NEXT(qi)

 

p

qi

qi

CH(Qi)

CH(Qi)

p

PREV(p)

PREV(p)

a)

!)

Рис. 1.2. Процесс получения из предыдущей опорной точки qi следующей. Новой опорной точкой становится Next(qi) (а), опорная точка не меняется (б).

3

Оценим суммарную сложность работы алгоритма:

-Разбиение множества P на подмножества Pi выполняется за время O(n);

-Так как в каждом подмножестве Pi не более чем m точек, построение выпуклых оболочек будет иметь суммарную сложность O(dmn em log m), то есть O(n log m);

-Выбор начальной вершины выпуклой оболочки осуществляется за время O(n);

-Алгоритм сделает h шагов, при этом на каждом шаге он затратит время O(dmn e) на линейный поиск следующей точки выпуклой оболочки среди правых опорных точек (без учета времени, потраченного на их поиск);

-Так как каждая точка исходного множества P либо является вершиной в точности одного выпуклого многоугольника CH(Pi), либо не является вершиной ни одного из них, и при этом каждая вершина при поиске опорных точек может быть пройдена не более чем два раза, то сложность подсчета всех опорных точек на всех шагах алгоритма составит O(n).

Таким образом, получается, что суммарная сложность алгоритма составляет O(n log m + hdmn e). Если в качестве m мы бы выбрали h, то сложность алгоритма свелась бы к O(n log h). Проблема заключается в том, что мы не всегда можем точно знать h в момент начала выполнения алгоритма. Поэтому предлагается подход, позволяющий подобрать значение h без увеличения сложность алгоритма.

Модифицируем алгоритм Chan-March-With-Param(P; m) так, чтобы он делал не более чем m шагов и в случае, если после последнего сделанного шага выпуклая оболочка CH(P ) еще не построена (текущая точка не совпала с начальной), то он сигнализировал бы об этом. Тогда алгоритм построения выпуклой оболочки будет выглядеть следующим образом:

algorithm Chan-March(P )! CH(P )

Вход. Исходное множество точек P = fpi j pi = (xi; yi); i 2 [1::n]g.

Выход. Выпуклая оболочка множества точек CH(P ), заданная последовательностью вершин (перечисленных в

порядке обхода против часовой стрелки).

1

 

for t à 1; 2; 3; : : :t do

 

 

 

m à min(n; 22 )

 

 

Вызвать модификацию Chan-March-With-Param(P; m)

 

 

if Алгоритм построил выпуклую оболочку CH(P ) then

 

 

Вернуть в качестве результата CH(P )

 

 

end-then

 

 

end-do

 

 

 

Очевидно, что алгоритм всегда завершится, поскольку для случая m = n, он представляет собой не что иное, как алгоритм Грэхема. Также очевидно, что алгоритм завершится, как только выполнится условие m ¸ h, то есть t ¸ dlog log he. При зафиксированном t время работы алгоритма составит O(n2t). Таким образом, к тому моменту, как алгоритм завершится, он проработает время:

 

dlog log he

 

Xi

O(

n2i) = O(n2dlog log he+1) = O(n log h)

 

=1

4

В алгоритме Чена подбирается параметр m, который определяет максимальный размер подмножеств, на которые разбивается исходное множество, а также максимальное количество шагов заворачивания. Как только параметр m становится больше или равным h (количеству крайних точек результирующей выпуклой оболочки) алгоритм успешно строит выпуклую оболочку и заканчивает работу. В качестве параметра m предлагается последовательно подставлять значения некоторой возрастающей последовательности mi до тех пор пока алгоритм не построит выпуклую оболочку. В оригинальной работе Чена в качестве такой последовательности

предлагается:

nmi = 22i o; i = 0; 1; 2; : : :

 

Доказывается также, что сложность алгоритма при применении такой последовательности для подбора составит O(n log h).

Однако, на практике достигнутый результат оказывается не настолько хорош. Продемонстрируем это следующим образом. Обратим внимание на первые шесть элементов последовательности fmig ; i = 0; 1; 2; : : :

f4; 16; 256; 65536; 4294967296; 18446744073709551616 : : : g

Очевидно, что для большинства разумных входных данных алгоритм не сделает больше чем шесть полных шагов. Напомним, что сложность одного полного шага алгоритма Чена для параметра m составляет O(n log m). Эта сложность включает в себя сложность построения частичных выпуклых оболочек для подмножеств исходного множества O(n log m), а также сложность m шагов заворачивания O(n).

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

Если рассмотреть два близких по распределению равномощные множества точек, в одном из которых h = 65536 + a, а в другом из которых h = 4294967296 ¡ b, где a и b относительно небольшие положительные константы, то алгоритм Чена для двух этих множеств будет работать с практически идентичными затратами по времени. При этом непосредственно из асимптотического характера сложности следовало бы предположить, что затраты по времени будут различаться примерно в два раза.

Эти и другие предпосылки позволяют предположить, что разумно было бы модифицировать алгоритм Чена с целью уменьшения числа его шагов (при этом сделав каждый из них менее трудоемким), чтобы избежать подобных ситуаций.

Заметим, что более естественной последовательностью подбора параметра m является последовательность:

©mi = 2iª; i = 0; 1; 2; : : :

В таком случае, алгоритм сделает не более чем dlog he полных шагов, так как на каждом очередном шаге m возрастает в два раза. Однако, если при данной последовательности оставить остальные элементы алгоритма Чена без изменений, то простой анализ даст сложность O(n log2 h), что неприемлемо. Для того, чтобы снова достигнуть асимптотической сложности O(n log h) необходимо модифицировать также основной шаг алгоритма Чена.

Воспользуемся тем, что максимальный размер подмножества m на каждом шаге возрастает в два раза. Тогда каждая группа точек на новом шаге может быть представлена как объединение не более чем двух групп точек с предыдущего шага, что позволяет, воспользовавшись процедурой объединения двух выпуклых оболочек, осуществить переход между соседними шагами за линейное время O(n) без построения выпуклых оболочек нового разбиения заново. Это возможно благодаря тому, что выпуклая оболочка объединения двух выпуклых оболочек с количеством крайних точек a и b может быть построена за O(a+b). Если из k подмножеств, на которые разбито множество из n точек выбрать dk2 e пар подмножеств и применить процедуру объединения к этим парам, то будет затрачено O(n) операций, поскольку каждое из подмножеств будет участвовать в объединении не более одного раза (если k нечетно, то останется также одно подмножество, которое не будет задействовано в процедуре объединения).

Получается, что каждый полный шаг будет иметь суммарную сложность O(n), при этом алгоритм сделает не более чем dlog he полных шагов, что приводит к простому выводу оценки сложности алгоритма O(n log h).

Соседние файлы в папке Выпуклые оболочки