Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
фильтр (?/|У)Д,{р: p^U и p<V). Ясно, что шаг «слияния» в методе «разделяй и властвуй» сводится к вычислению множества фильтр(тах(5[) |max(S2)). Таким образом, получаем следующий простой алгоритм:
4.1. Расширения и варианты
199
function МАКСИМУMbI2(S,rf) begin if (151=1) then return 5
else begin(5i,S2) :== разбиение S пополам no xd;
Mx := МАКСИМУМЫ2(5,, d);
M2 := МАКСИМУМЫ2(52>^);
return M2 (J фильтр (M{ j M2)
end
end.
Если обозначить через 7^(|5|) время обработки процедуры МАКСИМУМЫ2(5), а через /Vi(|Si|, \S2\) время, необходимое для вычисления множества фильтр(5i|52) '), то сразу получаем следующее рекуррентное соотношение (здесь предполагается, что N — четное число):
Td (N) < 2Td (NJ2) + Fd_t {N12, N/2) + О (N), (4.8)
где О (N) —время, используемое на разбиение множества 5 на равные части Si и S2.
Очевидно, что основные затруднения в рассматриваемом методе связаны с вычислением множества, названного нами фильтром. Предположим снова, что U и У —два множества точек в Еа, определенные как это сделано выше, и \U\ = и, a \ V\ = = v. Воспользуемся еще раз методом «разделяй и властвуй». Разделим V пополам по xd~i на (Vi, V2) и обозначим через xd-i наибольшее значение координаты xd-i точек из V\. Величина Xd-i разбивает U на (U\, U2). Рис. 4.6 иллюстрирует эту ситуацию. На этом рисунке показаны проекции множеств U и V на плоскость (xd, хы). Заметим, что \Vi\aiv/2 и \V2\=av/2, в то время как \Ui\ — пг и \02\ = и — пг, где пг— некоторое целое число. При таком разбиении множеств исходная задача вычисления множества фильтр (U\ V) заменяется четырьмя подзадачами вычисления множеств фильтр (l)\ \ V\), фильтр {U\ \ V2), фильтр(U21 V\) и фильтр(U2\V2). Отметим, однако, что множество фильтр(U2\Vi) вычисляется тривиально, так как для каждой р е U2 и q <= Vi имеем xd(p) <; xd(q) и xd-i(p) > xd-i(q). Кроме того, каждый элемент из V2 доминирует над каждым элементом из Ui по координатам Xd и Xd-i, так что подзадача вычисления множества фильтр (Ui | V2) имеет в действительности размерность d — 2. Две оставшиеся подзадачи по-прежнему имеют размерность d—1, но относятся к множествам с меньшим числом элементов. Наглядно процесс вычисления можно
') Следует объяснить индексы, использованные в записи: Т( ) и F(,). Множество 5 — это множество точек в Е". Однако, так как каждая точка множества 52 доминирует над каждой точкой множества St по координате Xd, то вычисление множества фильтр (S,|S2) является фактически (d — 1)-мерной задачей.
200 Гл. 4. Выпуклые оболочки: расширения и приложения
представить как прохождение путей, порождаемых двойной рекурсией: по размерам обрабатываемых множеств и по размерности. Первая заканчивается, когда мощность одного из двух множеств пары становится маленькой (равной единице), вторая завершается, когда размерность становится настолько маленькой, что применим прямой эффективный метод (это имеет место
и V
Рис. 4.6. Вычисление множества фильтр(U| V) методом «разделяй и властвуй» (путем сведения к трем более простым подзадачам).
при размерности, равной 3, когда можно воспользоваться модификацией метода заметания по измерению, описанного ранее). Более формально алгоритм описывает следующая функция (заметим, что в алгоритме МАК.СИМУМЫ2 множество фильтр (М i\M2) вычисляется в результате обращения к ФИЛЬТР (Мь М2; d-1)):
function ФИЛЬТР^,V; d) begin if (d = 3) then A := ФИЛЬТР2(?/, V);
if (V = {q}) then A:={p: p^U и p<q}\ if (U = {p}) then
begin if for each q ^V: p <?q then A := {p} else A := 0
end
else begin (V, ,V2) '¦— разбиение V пополам no xd; xd = max {xd (p): pel/,}; {Uy,U2) := части, на которыеxd разбивает U; А :=ФИЛЬТР(с/2,1/2; d) U (ФИЛЬТР(с/,, Vu- d)[\<b\\nhlV{Ui,V2\d- 1))
end; return A
end.
4.1. Расширения и варианты
201
Осталось описать процедуру ФИЛЫР2. Эта процедура использует метод заметания и аналогична процедуре МАКСИМУМЫ! для d = 2. Точки множества U U V просматриваются в порядке уменьшения координаты х2 и помещаются в очередь Q. Если текущая точка р принадлежит V, то М изменяется, в противном случае р либо добавляется к М (как максимальный элемент), либо исключается из рассмотрения. Таким образом, имеем function ФИЛЬТР2(с/,1/) begin Q := упорядочить U\jV в порядке убывания координаты xd; М:=0; х\:=0;
while (Q Ф 0) do begin p<=Q;
if (xx (p) > jcI) then
begin if (pe[/) then M :==M[){p} (¦является максимальным элементом*) else x\:=xx(p)
end
end; return M
end.
Для анализа работы алгоритма обозначим через Fd(u, v) время обработки процедуры ФИЛЬТР(U, V; d). Анализ процедуры ФИЛБТР2 непосредственно дает F2(u, v) = О(и + v) (при условии что U и V предварительно упорядочены по значению координаты х2). В общем случае, анализируя процедуру ФИЛЬТР, получаем следующее рекуррентное соотношение:
Fd (и, v) < Fd (от, v/2) + Fd (и - от, v/2) + Fd_y (m, v/2), (4.9)
где m — некоторое целое число 0 ^ m и. Довольно утомительные вычисления ') с учетом оценки для F2 показывают, что максимальное значение правой части соотношения есть 0((и + w)log«(log v)d~3). С учетом этого неравенство (4.8) принимает вид
