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

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

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 36 37 38 39 40 41 < 42 > 43 44 45 46 47 48 .. 180 >> Следующая


Следующая теорема характеризует выпуклые оболочки в нужном нам плане.

Теорема 3.1 (McMullen, Shephard (1971)]. Выпуклая оболочка конечного множества точек в Ей является выпуклым политопом. Наоборот, каждый выпуклый политоп является выпуклой оболочкой некоторого конечного множества точек.

Выпуклый политоп задается описанием его границы, состоящей из граней. Каждая грань выпуклого политопа является выпуклым множеством (т. е. выпуклым политопом более низкой размерности); k-грань обозначает ^-мерную грань (т.е. грань, аффинная оболочка которой имеет размерность k). Если политоп Р имеет размерность d, то его (d — I)-грани называются гипергранями, (d — 2)-грани — подгранями, 1-грани — ребрами, а 0-грани — вершинами. Ясно, что ребра и вершины сохраняют свое привычное значение в пространствах любой размерности. Для 3-политопа гиперграни являются плоскими многоугольниками, а подграни и ребра совпадают. Как мы уже видели ранее, эти четыре класса граней играют важную роль в алгоритмах построения выпуклой оболочки. Для единообразия может оказаться полезным называть d-политоп af-гранью, а пустое множество в такой терминологии превращается в (—1)-грань. Если Р является выпуклой оболочкой конечного множества точек 5 в Еа, то грань политопа Р является выпуклой оболочкой подмножества Т множества 5 (т. е. она определяется подмножеством множества S). Однако не все подмножества 5 определяют грани.

118

Гл. 3. Выпуклые оболочки: основные алгоритмы

Политопы некоторых типов заслуживают особого внимания. rf-политоп Р называется d-симплексом (или кратко симплексом), если он является выпуклой оболочкой (d+ 1) аффинно независимых точек. В этом случае каждое подмножество из этих d вершин само является симплексом и является гранью Р. Таким образом, каждая й-грань содержит 2*+' граней ') (размерностей k, k—\.....О, —1). Например, для d = 0, 1, 2 и 3 соответствующий симплекс является точкой, ребром, треугольником и треугольной пирамидой. Заметим, что треугольная пирамида (3-грань в соответствии с принятым соглашением) содержит одну 3-грань (сама пирамида), четыре 2-грани (треугольники), шесть 1-граней (ребра), четыре 0-граней (вершины) и одну (—1)-грань (пустое множество), что вместе составляет 16 = = 24 граней.

Симплициальным называется d-политоп, каждая гипергрань которого является симплексом. Это эквивалентно тому, что каждая грань симплициального d-политопа содержит в точности d подграней. С другой стороны (можно было бы сказать «двойственной»), d-политоп называется простым, если каждая из его вершин инцидентна в точности d ребрам. В самом деле, легко понять, что симплициальный политоп является двойственным по отношению к простому политопу при понимании двойственности, как это принято в общей топологии, как отображения, отображающего множество размерности s ^ d в множество размерности d — s (обратите также внимание на более специальное отношение двойственности, воплощаемое полярными преобразованиями, рассмотренными в разд. 1.3.3). Симплициальные и простые политопы являются чрезвычайно важными не только из-за их структурной привлекательности и — простите за игру слов — простоты, но также ввиду того, что они естественным образом возникают в двух типичных (и двойственных!) ситуациях. В самом деле, обратимся для конкретности к хорошо знакомому трехмерному пространству. Выпуклая оболочка конечного множества точек, находящихся в общем положении, является симплициальным 3-политопом (вероятность того, что более трех точек лежат в одной плоскости, равна нулю), вместе с тем пересечение конечного множества полупространств, находящихся в общем положении, является простым 3-политопом.

Комбинаторной природе политопов, и в частности взаимосвязи между числом граней и размерностью, было уделено значительное внимание. Достаточно напомнить здесь, что число

') Действительно, в этом случае множество всех подмножеств множества вершин является множеством граней. Как хорошо известно, диаграмма Хас-се для этого множества представляет (k + 1) -мерный куб. Такая диаграмма обычно называется графом граней политона.

3.1. Предварительные сведения

19

F(d, N) гиперграней d-политопа с N вершинами может доходить до (см.[Klee (1966)])

Короче можно сказать, что F(d, Л/) = О (A/Ld/2J). То, что число гиперграней в худшем случае растет экспоненциально в зависимости от числа вершин и наоборот (в соответствии с принципом двойственности), приводит к серьезным затруднениям при представлении rf-политопов для больших значений d. К счастью, ситуация оказывается значительно более простой для таких важных случаев, как d = 2, 3. В частности, для d = 2 политоп является выпуклым многоугольником. Важно понимать, что многоугольник— независимо от того, является ли он выпуклым или нет, — представляет упорядоченную последовательность вершин. Такую последовательность можно адекватно представить как массивом, так и двусвязным списком.

В трехмерном случае проблемы, связанные с представлением, также не очень серьезные. Многогранник может быть полностью определен перечислением его вершин, ребер и граней. В соответствии с формулой Эйлера (разд. 1.3.1) число вершин ребер и граней трехмерного многогранника связано линейным соотношением, откуда следует, что для полного описания (представления) многогранника с N вершинами достаточно объема памяти 0(N). Более того, скелет такого многогранника (множество его ребер) является планарным графом1), так что мы можем представить многогранник, используя любую структуру данных, подходящую для представления планарного графа (такие как список смежности или реберный список с двойными связями, описанные в разд. 1.2.3.2).
Предыдущая << 1 .. 36 37 38 39 40 41 < 42 > 43 44 45 46 47 48 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed