Триангуляции выпуклых многогранников

• Автор: Груздев, Дмитрий Валентинович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Нижний Новгород
• Количество страниц: 148 с.

1. Модификация алгоритма Фурье-Моцкина для построения триангуляции

1.1 Основные определения и свойства

1.1.1 Точечные конфигурации и выпуклые многогранники

1.1.2 Симплициальныс комплексы и множества правильно расположенных симплексов

1.1.3 Триангуляции точечных конфигураций

1.1.4 Триангуляции границ точечных конфигураций

1.1.5 Модели вычислений и временная сложность алгоритмов

1.2 Алгоритм Фурье-Моцкина и его предлагаемая модификация

1.3 КТФМ-алгоритм

1.4 Свойства КТФМ-алгоритма

1.4.1 Изоморфизм симплициалыюго комплекса граней получаемой КТФМ-алгорнтмом триангуляции границы точечной конфигурации симплициально-му комплексу собственных граней некоторого симплициального политопа
1.4.2 Нременная сложность КТФМ-алгоритма и его оптимальность в пространствах нечетной размерности
1.4.3 Первый и второй ТФМ-алгоритмы
1.4.4 Количественные свойства получаемых КТФМ-алгоритмом триангуляций
2. Модификация алгоритма Фурье-Моцкина для построения триангуляции и ее развертки
2.1 Основные определения и свойства
2.1.1 Развертка симплициального комплекса
2.1.2 Звездная развертка симплициального комплекса
2.2 Развертка симплициального комплекса собственных граней симплнциаль-

ного политопа
2.3 Отношение предшествия на получаемой КТФМ-алгоритмом триангуляции границы точечной конфигурации
2.4 КРТФМ-алгоритм
2.5 Модификация алгоритма Фурье-Моцкииа для построения триангуляции и ее знедной развертки (ЗРТФМ-алгоритм)
3. Вопросы существования симплициальных комплексов с некоторыми нетривиальными свойствами
3.1 Пример разворачиваемой триангуляции, не имеющей звездной развертки
3.2 Целочисленный пример неразворачиваемой триангуляции точечной конфигурации и следствие из него
3.3 Триангуляция границы 3-мерного куба, для которой не существует порождающей ее триангуляции 3-мерного куба
3.4 Пример недополняемости множества тетраэдров до триангуляции
3-мериой точечной конфигурации
3.5 Пример недополняемости множества 4-мерпых симплексов с общей вершиной до триангуляции 4-мерной точечной конфигурации
4. Характеристики триангуляций некоторых выпуклых многогранников
4.1 Основные определения и свойства
4.1.1 /-векторы триангуляций границ точечных конфигураций
4.1.2 /-векторы триангуляций точечных конфигураций
4.2 Минимальные триангуляции трехмерных выпуклых многогранников из некоторых классов
4.3 Описание множеств /-векторов триангуляций 4-мерного куба и распределений объема 4-мерного куба по симплексам его триангуляций
4.3.1 Основные определения и обозначения
4.3.2 Исследование симплексов, вершины которых являются вершинами

4-мерного куба
4.3.3 Исследование триангуляций 4-мерного куба
4.4 Описание множеств /-векторов триангуляций границы 4-мерного куба и распределений 3-мерного объема границы 4-мерного куба по симплексам его триангуляций
4.5 Описание множества /-векторов триангуляций границы 5-мерного куба
Литература

1.4. Свойства КТФМ-алгоритма.
1.4.1. Изоморфизм симплициального комплекса граней получаемой КТФМ-алгоритмом триангуляции границы точечной конфигурации симплициальному комплексу собственных граней некоторого симплициального политопа.
Заметим, что в общем случае неверно утверждение об изоморфности сим-нлициалвного комплекса граней триангуляции границы точечной конфигурации симплициальному комплексу собственных граней некоторого симплици-альпого политопа и в разделе 3.2 показано существование примера триангуляции границы ТЭ(Л') некоторой 4-мерной точечной конфигурации А', сим-плицпальный комплекс Г(ТЭ(Л')) граней которой не является изоморфным симплициальному комплексу собственных граней ни одного симплициально-го политопа. Однако, в случае КТФМ-алгоритма, как мы сейчас увидим, все обстоит иначе.
Рассмотрим точечную конфигурацию, заданную последовательностью своих точек Лдг = (я] йдг) £ Ал, и точку а0 £ тЩ«! сы-ц]). Положим По — и] — ... — илл-1 — 0* Ап — (п 1 и Ап — {п] при п = (I + I Получив на входе последовательность точек А^ и вектор иы = (м,г+2 пл/), где ud+2,^^■,UN 6 { — 1,4-1}, КТФМ-алгоритм последовательно при п = й + 1 N построит, в частности, 3-триангуляцию //„ = СТРМэ{Ап,ип) £ Тд{Лп), где ип - (и^+2 «п). Мы покажем, что симилициальный комплекс Г(//„) изоморфен симплициальному комплексу граней некоторого симплициального политопа.
Для простоты изложения рассмотрим случай 0 = а0 £ тЦ^-ц]). Заметим, что данное требование не уменьшает общности рассмотрения, так как систему координат всегда можно выбрать так, чтобы ее центр был внутренней точкой а0 симплекса [аь... ,а^+1].
При п = (I + 1 N — 1 положим Н~ = {Г £ Нп : (Ьр",ап+1) < 0}, Н° = {/" £ //„ : (Ь^,7ЩТ) = 0} и //+ = {^ £ //„ : (б£",а^ГГ) > 0}.
Обозначим при п = (1+1,.через 1{АП) = {г £ {1,... ,п} : а,[Л;-)]}