Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
function МАКСИМУМЫl{S,d)
1. begin М:= 0;
2. Л4*:=0; (* М и М'— это множества максимумов соответственно по d и d — 1 измерениям *)
3. whiIe(Q=^ 0) do
4. begin p<=Q (* выбрать элемент из очереди*)
196
Гл. 4. Выпуклые оболочки: расширения и приложения
5.
6. 7.
р* := проекция р на (xt.....Xd-iY,
if(p* < ЛГ) then begin ЛГ:= МАКСИМУМЫ 1(ЛГ U {р'},
8.
М:— M\J {р}
end;
9.
end; return М
end.
Говоря на описательном уровне, функция МАКСИМУМЫ 1 выполняет заметание точек множества 5 в порядке убывания координаты xd и для каждой точки р определяет (пункты 5, 6), доминирует над ней или нет по координатам хи х2, ..., xd-\ какая-либо из уже просмотренных точек (эти точки уже доминируют над р по координате ха в соответствии с организацией процедуры заметания). Тем самым обеспечивается корректность этого подхода, критическим местом которого являются, как это очевидно, пункты 6 и 7: «если р*^М*, то М* := МАКСИМУМЫ! (M*\J {р*}, d— 1)». По существу, это не что иное, как последовательное (т. е. по одной точке за один раз) построение максимумов (d — 1) -мерного множества. Это совсем не тривиальная задача. Эффективный способ ее решения известен лишь для d = 2, 3.
В самом деле, для d = 2 множество М* является одномерным (а значит, оно содержит лишь один элемент) и проверка условия «р* < ЛГ*?» сводится к проверке «х{ (рХ^ = max х{ (q)?».
При этом операция по изменению множества М* М* := МАКСИМУМЫ! (ЛГ* U {р*}, d — 1)
превращается в следующее присваивание xi :== Xi(p). Как операция проверки, так и операция присваивания могут быть выполнены за постоянное время. Для d = 3 ситуация естественно является более сложной, но по-прежнему остается управляемой. В этом случае М* — двумерное множество максимумов (рис. 4.4) — является линейно упорядоченным и может быть организовано в виде сбалансированного по высоте дерева поиска но координате х2. Проверка условия «р* <( ЛГ ?» превращается в поиск х2(р*) в этом дереве: если x2(q) следует непосредственно за х2(р*), то имеет место эквивалентность
(рХМ*)^^ (р'Хдг, (q). Корректировка множества М* в случае р* < М* производится в результате прохождения дерева, начиная с х2(р*), в «направлении» уменьшения координаты х2. При этом удаляются все элементы множества до тех пор, пока не будет найдена первая
4.1. Расширения и варианты
197
точка q', для которой Xi(q') >Х\(р*). Легко найти, что время, затрачиваемое на решение этой задачи в целом, составляет 0(N log N), так как на каждую проверку «р*-<ЛГ?» (с возможной вставкой элемента в дерево) требуется время O(IogN), в то время как каждая операция удаления элемента при прохождении дерева в процессе его изменения может быть выполнена за постоянное время путем тривиального изменения дерева поиска (прошиванием). Учитывая, что производятся N операций
Ъ(Р*)-^ ^—xz(q)
Рис. 4.4. Множество максимумов М* можно линейно упорядочить. При этом проверка условия «р* <( Af*?» заключается в сравнении Xi-координаты точки р* с хгкоординатой ближайшей к р* точки множества М', расположенной
«проверить — вставить» и не более N операций «удалить», получаем указанную оценку. Если вспомнить, что метод заметания требует предварительной сортировки, приходим к выводу, что в случае d = 2, 3 время работы алгоритма МАКСИМУМЫ 1 является оптимальным и составляет в (ЛГ log Л/).
К сожалению, насколько нам известно, уже для d = 4 этот метод имеет оценку 0(N2). Так что необходимо искать иной подход к решению этой задачи. Один из возможных подходов основывается на методе «разделяй и властвуй». Как будет видно из дальнейшего, соответствующий алгоритм предполагает, что множества точек по очереди разбиваются на части в соответствии со значениями координат Xd, Xd-i, . ¦ ¦ , х2. Поэтому, чтобы облегчить выполнение этих часто используемых в алгоритме операций, удобно ввести некоторый шаг предварительной обработки. Этот шаг заключается в сортировке элементов множества 5 по каждой из координат. Результирующая структура данных представляет многосвязный список ((d—1)-кратно прошитый список), каждый узел которого прошит каждым из
198 Гл. 4. Выпуклые оболочки: расширения и приложения
односвязных списков, соответствующих выбранным координатам. Для создания такой структуры данных требуется время О (dN log N). Эта структура позволяет легко и эффективно разбивать множество на части. Избегая тяжеловесных оборотов, будем говорить, что х, разбивает S на (Si, S2), если для каждой p<^S] имеем х,(р) ^ л:/, а для каждой ?eS2 имеем Xj(q) > х,-. Будем также говорить, что S разбито пополам по х,-на (Sb S2), если Xj разбивает S на (Si, S2) и х,- является медианой множества точек S по координате х\ (так что |Si| ~
Первым шагом алгоритма поиска всех максимумов МАКСИМУМЕ^ является разбиение пополам заданного множества S по координате xd на (Sb S2). Затем алгоритм рекурсивно применяется к множествам Si и S2. В результате получаются два
множества соответствующих им максимумов max (Si) и max(S2). При объединении результатов двух рекурсивных обращений к процедуре следует учитывать, что все элементы множества max(S2) являются также максимумами S, в то время как для элементов max(Si) это может не иметь места. Действительно, элемент множества max (Si) является максимальным элементом S тогда и только тогда, когда над ним не доминирует ни один из элементов множества max(S2). Соответствующая ситуация показана на рис. 4.5 для случая d = 3. Таким образом, если U и V — два множества точек таких, что для всех ре (/ и q «= V имеет место Xd(p) ^ xd(q), то удобно определить новое множество фильтр (U \ V)cz U:
