Научная литература
booksshare.net -> Добавить материал -> Математика -> Препарата Ф. -> "Вычислительная геометрия: Введение" -> 60

Вычислительная геометрия: Введение - Препарата Ф.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 54 55 56 57 58 59 < 60 > 61 62 63 64 65 66 .. 180 >> Следующая


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), равной максимальному числу подграней
Предыдущая << 1 .. 54 55 56 57 58 59 < 60 > 61 62 63 64 65 66 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed