Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
procedure ЗАВОРАЧИВАНИЕ-ПОДАРКА(р,, ря) 1. begin Q:= 0; Т := 0;
2. F := найти некоторую исходную гипергрань выпуклой оболочки;
3. д~ <= подграни гиперграни F;
4. Q<=F;
5. while(Q ф 0) do
6. begin F<=Q(* выбрать первый элемент
из очереди *)
7. Г := подграни гиперграни F;
6*
164
Гл. 3. Выпуклые оболочки: основные алгоритмы
9.
8.
for each ееГП^" do (* е является кандидатом для шага "заворачивания подарка"*)
begin F' := гипергрань, смежная с F по
10.
е (*"заворачивание подарка"*) вставить в W все подграни F', которых еше нет в файле, и
удалить те из них, которые там уже имеются;
11.
Q<=F'
12.
end;
выдать F
end
end.
Этот алгоритм содержит несколько основных этапов, реализацию которых необходимо теперь проанализировать более подробно:
Шаг 2: Найти некоторую исходную гипергрань выпуклой оболочки.
Шаг 7: Построить подграни гиперграни F.
Шаг 8: Проверить, является ли подгрань е кандидатом на использование в последующей обработке. Шаг 9 представляет собой шаг «заворачивания подарка», обсуждавшийся ранее.
Рассмотрим теперь каждую из указанных операций и оценим их сложность.
Шаг 2. «Найти некоторую исходную гипергрань выпуклой оболочки». Идея состоит в том, чтобы путем последовательной аппроксимации получить гиперплоскость, содержащую гипергрань выпуклой оболочки. То есть путем построения последовательности из d опорных гиперплоскостей щ,л2, ..., па, каждая из которых имеет с выпуклой оболочкой на одну общую вершину больше, чем предыдущая гиперплоскость. По сути, этот метод является видоизменением механизма «заворачивания подарка», когда на /-й из d итераций гиперплоскость я/ содержит (/—¦ 1)-грань выпуклой оболочки. Таким образом, процедура начинается с определения точки с наименьшей первой координатой (х\). Назовем эту точку р\. Эта точка со всей очевидностью является вершиной (0-гранью) выпуклой оболочки. Поэтому, гипергрань Я1 выбирается ортогональной вектору (1, 0, . . . , 0) и при этом должна проходить через точку р\. Сделав таким образом начальную итерацию, на /-й итерации (/ = 2, . . . . . . , d) получим гиперплоскость с нормалью л; р содержащую вершины р\, р'2, . . ., р'1_1. Вектор а; выбирается ортогональ-
3.4. Выпуклые оболочки размерности большей двух
165
ным к нормали п,-_ь каждому из (/ — 2) векторов р[р'2, p\p'v . . . ¦ ¦ p'jp'i-i и каждой из координатных осей Xj+i, Xj+2, xd. Эти (d—1) условий определяют вектор а;, и, следовательно, теперь можно выполнить основную операцию по «заворачиванию», использовав для этого векторы а,- и п/_ь На рис. 3.26 показана последовательность гиперплоскостей для случая d = 3. Вычислительные затраты на каждой итерации связаны главным
Рис. 3.26. Последовательность гиперплоскостей (ль я2, л3) такова, что я3 содержит гипергрань, которая берется в качестве исходной для процедуры построения выпуклой оболочки.
образом с построением вектора а/ и выбором очередной точки р^. Последняя операция имеет сложность O(Nd), в то время как для определения вектора а/ требуется лишь время 0(d2), так как а; получается в результате добавления в точности одного линейного ограничения к ограничениям, определяющим вектор а/_ь Таким образом, поскольку выполняется d итераций, построение исходной грани завершается за время 0(Nd2) -f-+ 0(d3) = 0(Nd2), учитывая при этом, что N ^ d.
Шаг 7. «Построить подграни гиперграни F». В силу сделанного предположения о симплициональности политопа каждая гипергрань определяется в точности d вершинами, а каждое подмножество, содержащее (d— 1) вершин гиперграни F, определяет подгрань. Таким образом, можно за время 0(d2) очевидным способом построить подграни гиперграни F. Каждая гипергрань будет описываться d-компонентным вектором индексов ее вершин, а подгрань — аналогичным (d—1)-компонентным вектором.
Шаг 8. «Проверить, является ли подгрань е кандидатом на использование в последующей обработке». Подгрань является
Гл. 3. Выпуклые оболочки: основные алгоритмы
кандидатом, если она содержится лишь в одной грани, порождаемой алгоритмом, и, следовательно, если поддерживается файл &~ таких подграней, то требуемым тестом является просмотр этого файла. Как отмечалось выше, подгрань описывается (d— 1)-компонентным вектором из целых чисел (индексов определяющих ее вершин). Можно упорядочить файл д~ в соответствии с лексикографическим порядком и хранить его в виде сбалансированного по высоте бинарного дерева поиска. Если имеется некоторая подгрань е, то потребность в доступе к Т может возникнуть в двух случаях: либо для проверки принадлежности е к числу кандидатов (шаг 8 алгоритма), либо для изменения файла (шаг 10 алгоритма). В первом случае просматривается файл ?Г и определяется, содержит ли он е. Во втором случае также происходит просмотр файла 0~ с целью определения принадлежности е файлу, но, кроме того, если е уже содержится в файле, то она удаляется, в противном случае она добавляется в файл. В обоих случаях просмотр файла осуществляется за время O(dlogM), где М — размер файла, ограниченный сверху величиной SF(d, N), равной максимальному числу подграней