Содержание к диссертации
Введение
1. Модификация алгоритма Фурье-Моцкина для построения триангуляции 23
1.1 Основные определения н свойства 23
1.1.1 Точечные конфигурации и выпуклые многогранники 23
1.1.2 Снмплнциальные комплексы и множества правильно расположенных симплексов 25
1.1.3 Триангуляции точечных конфигураций 27
1.1.4 Триангуляции границ точечных конфигураций 28
1.1.5 Модели вычислений и временная сложность алгоритмов 31
1.2 Алгоритм Фурье-Моцкина и его предлагаемая модификация 34
1.3 КТФМ-алгоритм 39
1.4 Свойства КТФМ-алгоритма 50
1.4.1 Изоморфизм симплнциалыюго комплекса граней получаемой КТФМ-алгоритмом триангуляции границы точечной конфигурации симплициалыю-му комплексу собственных граней некоторого симплнциалыюго политопа. 50
1.4.2 Временная сложность КТФМ-алгоритма и его оптимальность в пространствах нечетной размерности 57
1.4.3 Первый н второй ТФМ-алгоритмы 61
1.4.4 Количественные свойства получаемых КТФМ-алгоритмом триангуляции 05
2. Модификация алгоритма Фурье-Моцкина для построения триангуляции и ее развертки 69
2.1 Основные определения и свойства 69
2.1.1 Развертка симплнциалыюго комплекса 69
2.1.2 Звездная развертка симплнциалыюго комплекса 70
2.2 Развертка симплнциалыюго комплекса собственных граней симплнцнального политопа 73
2.3 Отношение предшествия па получаемой КТФМ-алгорнтмом триангуляции границы точечной конфигурации 77
2.4 КРТФМ-алгоритм 82
2.5 Модификация алгоритма Фурье-Моцкппа для построения триангуляции и се зведной развертки (ЗРТФМ-алгорнтм) 87
3, Вопросы существования симллициальных комплексов с некоторыми нетривиальными свойствами 89
3.1 Пример разворачиваемой триангуляции, не имеющей звездной развертки 89
3.2 Целочисленный пример неразворачиваемой триангуляции точечной конфигурации и следствие из пего 91
3.3 Триангуляции границы 3-мерного куба, для которой не существует порождающей се триангуляции 3-мсрного куба 95
3.4 Пример недополняемости множества тетраэдров до триангуляции 3-мерной точечной конфигурации 97
3.5 Пример педополняемости множества 4-мерных симплексов с общей вершиной до триангуляции 4-мерной точечной конфигурации 99
4. Характеристики триангуляции некоторых выпуклых много гранников 102
4.1 Основные определении и свойства 102
4.1.1 векторы триангуляции границ точечных конфигураций ,.. 102
4.1.2 векторы триангуляции точечных конфигураций 103
4.2 Минимальные триангуляции трехмерных выпуклых многогранников из некоторых классов 106
4.3 Описание множеств /-векторов триангуляции 4-мерного куба и распределений объема 4-мерного куба по симплексам его триангуляции 113
4.3.1 Основные определения и обозначения 113
4.3.2 Исследование симплексов, вершины которых являются вершинами 4-мерного куба 115
4.3.3 Исследование триангуляции 4-мерного куба 123
4.4 Описание множеств /-секторов триангуляции границы 4-мерного куба и распределений 3-мерного объема границы 4-мерного куба по симплексам его
триангуляции 132
4.5 Описание множества /-векторов триангуляции границы 5-мерного ку
ба 136
Литература
- Снмплнциальные комплексы и множества правильно расположенных симплексов
- Звездная развертка симплнциалыюго комплекса
- Целочисленный пример неразворачиваемой триангуляции точечной конфигурации и следствие из пего
- Минимальные триангуляции трехмерных выпуклых многогранников из некоторых классов
Введение к работе
К построению и исследованию триангуляции точечных конфигураций и выпуклых многогранников, являющихся выпуклыми оболочками конечного множества точек и называемых также политопами, приводят, в частности, задачи, возникающие в следующих областях: вычислительной геометрии, теории выпуклых многогранников, целочисленного линейного программирования. Триангуляция выпуклого многогранника является правильным (грапь-в-грань) его разбиением на симплексы и используется, например, для нахождения числа целочисленных точек выпуклого многогранника и точного вычисления его объема.
Фундаментальный факт теории линейных неравенств — теорема Мпнковского-Нсйли — утверждает, что множество М С \\d является политопом тогда и только тогда, когда М совпадает с множеством решений некоторой конечной системы линейных неравенств и ограничено, причем если Л/ является (/-мерным политопом, то такой системой является система неравенств, соответствующих гппергранпм политопа М (при этом данная система оказывается неприводимой). Для перехода от одного описания политопа к другому в разное время было предложено несколько алгоритмов. Одним из них и, по всей вероятности, первым по времени создания является алгоритм Минковского, требующий для начала работы всего входного описания политопа и непосредственно следующий из теоремы Минковского-Вейля. Другим алгоритмом является алгоритм Фурье-Моцкина, основная идея которого, восходящая к Фурье и развитая МОЦЕШНЫМ, выражена в методе двойного описания [15, ЗС] (см. также [18]) и методе "под-и ад" [17, 39]. Пусть (•/-мерный политой М задан выпуклой оболочкой конечного множества точек Л = {«!,... ,OJV} С Rd- Алгоритм Минковского для каждого аффппно независимого rf-элсментного подмножества Л С Л, по одну сторону аффинной оболочки которого располагаются все точки множества Л, получает неравенство, задающее соответствующее полупространство. Полученная система неравенств является выходом алгоритма Минковского, который, таким образом, имеет временную сложность 0(Nd). В то же время алгоритм Фурье-Моцкина, являясь итерационным, на каждой итерации получает очередную точку множества А и строит систему неравенств, описывающую выпуклую оболочку полученного множества точек, что позволяет оценить временную сложность его модификации (метод "под-над") величиной 0(ArLrf/2J+1).
Большое внимание, начиная с работы [3], уделяется изучению так называемых правильных (регулярных) триангуляции и разбиений, находящих приложения в теории дифференциальных уравнений. Для их построения приходится находить вупуклую оболочку множества точек в пространстве на единицу большей размерности. Таким же образом может быть построена и триангуляция Делоне [11], имеющая большое значение, например, для решения задачи о нахождении ближайших точек из некоторого конечного множества. Работа в пространстве па единицу большей увеличивает временную сложность алгоритмов. Поэтому другие способы построения триангуляции, работающие в исходном пространстве, также имеет смысл изучить тем более, что они допускают эффективные реализации (см. главу 1), полезные модификации (см. главу 2) и позволяют решать ряд задач (см. главу 4).
Диссертации является развитием идей и подходов к построению триангуляции, которые были рассмотрены и получили свое обоснование, например, в работах В.II. Шевченко [19, 20], C.W. Lee [45]. Данные идеи требовали создания реализующих и комбинирующих их эффективных алгоритмов построения триангуляции. Цель была достигнута созданием указанных алгоритмов как модификации алгоритма Фурье-Моцкина. Таким образом был создан КТФМ-алгоритм (комбинированный алгоритм Фурье-Моцкина для построении триангуляции) и его частные случаи: первый ТФМ-алгоритм и второй ТФМ-алгоритм.
Особый интерес при этом представляет гипотеза профессора В.II. Шевченко, согласно которой каждый /-вектор из множества /-векторов трпапгулн ции 7-мерных политопов достигается па трнангуляцинх, получаемых вторым ТФМ-алгорнтмом. Второй ТФМ-алгоритм является итерационным и, построчи па предыдущем этапе триангуляцию Т(Лп) уже рассмотренного множества точек Ап = {«і,...,ап}, при получении очередной точки an+i дополняет уже новыми симплексами до триангуллции всего множества полученных точек Т(Лп+і) — T(An)\jTn. При этом триангуляцией конечного множества точек (точечной конфигурации) А является правильное разбиение его выпуклой оболочки на симплексы с вершинами из А.
При изучении триангуляции точечных конфигураций важное место занимает свойство разпорачнваемости, так как симплпциальный комплекс граней разворачиваемой триангуляции (триангуляции, допускающей определенное упорядочивание своих симплексов, называемое ее разверткой) обладает многими замечательными свойствами (см., например, [52]). М.Е. Rudm в [48] построила пример неразворачиваемой триангуляции точечной конфигурации, состоящей из вершин тетраэдра и еще восьми точек на его гранях. Таким образом, имеет смысл постановка задачи одновременного построения триангуляции н ее развертки. Более того, структура получаемых вторым ТФМ-алгоритмом триангуляции привела к задаче построения развертки триангуляции Т(А,І+І) таким образом, чтобы последовательность ее первых симплексов совпадала с построенной на предыдущем этапе разверткой триангуляции Т(Ап). Обобщение указанного свойства привело к введению понятия звездной развертки и постановке задачи ее построения.
Для политопа могут быть поставлены: задача нахождения минимально возможного числа симплексов в его триангулпциях и более общая задача описания множества всех /-векторов его триангуляции. Разумеется, эти задачи теоретически можно решить полным перебором всех триангуляции, однако, практически найти все триангуляции не представляется реальным уже в сколь-либо нетривиальных случаях. Волее того, A. Below, J.Л. De Ьоега и Л. Uicliter-Gcbert показали в [33], что задача определения для произвольного трехмерного политопа Л/, имеющего п вершин, и произвольного натурального числа к, существует ли триангуляция политопа М, содержащая не более к симплексов, является NP-полной. Таким образом, не известен полиномиальный но сложности алгоритм относительно числа вершин понзволь-ного 3-мерного политопа, строящий триангуляцию данного 3-мерного политопа, состоящую из минимально возможного числа тетраэдров. Ясно [33], что данная задача остается NP-полной, если вместо класса трехмерных политопов М рассматривается класс (/-мерных политопов, где d 3. Задача построения триангуляции (f-мерного куба, содержащей минимально возможное число и{ 1) симплексов, привлекает внимание исследователей (P.S. Мага [47], R.W. Cottle [37], J. Bohm [34], J.F. Sallce [49, 50], U.H. Hughes [40, 41, 42] Todd M.J., Tuncel L. [53]) споим приложением для аппроксимации неподвижных точек непрерывного отображении (И. Scarf [51], см. также обзор в [53]). Для нахождения v{d) при d — 4,5 используется линейное программирование (J.F. Sallee [49], R.B. Hughes [41]), дающее нижнюю оценку числа f(t/), и непосредственное построение триангуляции для того, чтобы показать ее неулучшаемость и тем самым решить задачу.
ІЇ диссертации теоретическим фундаментом дли исследования задач о нахождении минимально возможного числа симплексов в трпангуляциях политопа и об описании множества всех /-векторов его триангуляции служит полученный профессором В.II. Шевченко в [20] аналог уравнений Дсна-Соммервиля дли триангуляции, связывающий возможные значения компонент /-вектора триангуляции политопа и порождаемой ею триангуляции его границы. Естественная схема решении данных задач состоит в том, чтобы с помощью алгоритмов триангуляции сгенерировать триангуляции, соответствующие всему возможному спектру значений исследуемой характеристики, и доказать, что других значений данная характеристика иметь не может. При этом следует заметить, что исследование свойств триангуляции политопа и составляющих их симплексов позволяет организовать процесс генерации триангуляции более целенаправленно.
Снмплнциальные комплексы и множества правильно расположенных симплексов
Конечное непустое множество С симплексов из Rrf называется симплици-альиым комплексом, если пересечение любых двух симплексов является их общей гранью и С содержит все грани своих симплексов. Симплексы из сим-плициального комплекса С называются его гранями, а размерностью dim(C) симплпциалыюго комплекса С называется максимальная размерность составляющих его симплексов. Симплнцпальный комплекс С называется однородным, если каждый симплекс из С принадлежит некоторому симплексу из С размерности dim(C). Таким образом, все максимальные по включению грани однородного симплпциалыюго комплекса С, называемые его гипергранями, и только они, имеют размерность tlim(C). В дальнейшем будут рассматриваться только однородные симплициальные комплексы, которые будем называть просто симплпппальными комплексами. Через Г;(С) обозначим множество {-мерных граней симплпциалыюго комплекса С, і = —1,0,...,dirn(C).
Симплициальные комплексы С\ и С2 назовем изоморфными, если между ними можно установить биекцию р, сохраняющую отношение включения: для любых граней Fi,F2 Є Сі включение Fi С F2 имеет место тогда и только тогда, когда y(Fi) Q vK a)- Такую биекцию 9 назовем изоморфизмом и заметим, что р сохраняет также и размерность: clim(F) = d\m( p{F)) для любой грани F є С\. Будем говорить, что симплексы, составляющие некоторое конечное множество, расположены правильно (грань-в-грань) [16, с, 24], если пересечение любых двух симплексов является их общей гранью. Таким образом, симплексы S и S расположены правильно, если S Л S = [Г0() П Г0(5")1- Заметим, что симплициальный комплекс можно определить эквивалентным образом как конечное непустое множество С правильно расположенных симплексов из IVі, которое содержит все грани своих симплексов.
Пусть II является конечным множеством правильно расположенных А-мерных симплексов. При і — -1,0,..., к множество Г;(Я) = Usef/ ГІ( ) назовем множеством г-мерных граней множества симплексов // и положим Т(П) Ut-i ГІ(Я) = и5є/7 Г()- Тогда имеют место
Лемма 1.1.4 Множество Т(Н) всех граней множества II правильно расположенных к-мерных симплексов является сштлициалъным комплексом.
Доказательство. Действительно, покажем, что если Fi,F2 Є F(/7), то F\ П F2 = [r0(Fi) П r0(F2)]. Рассмотрим Fu F2 Є Г(Н). Тогда существуют Su S2 Є /7 такие, что Iі) Є Г(5,-), і = 1,2. Поскольку симплексы из С расположены правильно, то F0 — S\ П Sz является симплексом. Рассматривая F- = F{ ҐІ F0 при і 1,2, видим, что F C] F2 = F[ ГІ F 2, Используя лемму 1.1.1 и то, что Fi, F0 Є Г(5;), получаем, что F- Є r(F0). Таким образом, из леммы 1.1.1 следует, что F[ f\F 2 = [\\{F[) П Г0 )] = [ВД) П r0{F0) Л r0(F3)]. Следовательно, P0(F0) = Г0(5іґі52) = Г0(51)ПГ0(52). Тогда FlC\F2 = F[f]F2 = [r0(Fi) П Г0(й)П r0(F2) П Го(52)] = [Г0(Г,) П P0(F2)]. Следовательно, Г(/7) является симилициальным комплексом. Лемма доказана.
Лемма 1.1.5 Пусть II = {Si,...,St} полется множеством правильно расположенных симплексов Тогда длп любой точки а Є \УТ=і ST существует единственная грань F Є Г{Н), содержащая точку а Є int(F) внутри себя cafT(F).
Доказательство. Поскольку а Є UT=I $V, ТО существует грань F Є Г(#), содержащая точку а Є int(F) внутри себя в afF(F). Теперь предположим, что существуют две различные грани Fi,F2 Є Г(Я), содержащие точку а внутри себя в afF(Fi) и в аіГ(ґ2) соответственно. Из леммы 1.1.4 следует, что Л ПГ2 = [Г0( )ПГ0( 2)]. Тогда а Є [r0(Fi)nr0(F2)], и так как а Є mt(Ft), то r0(Fi) С r0(F2). Аналогичным образом показывается, что r0(F2) С r0(Fi). Следовательно, F\ — F2 и предположение неверно. Таким образом, существует единственная искомая грань. Лемма доказана.
Для F Є Г(Я) через r{(F,H) = {Ґ Є I\(tf) ; F Є Г(Ґ)} обозначим множество тех симплексов из ГДЯ), гранью которых является F, и положим fi(F,H) = Г,-( Я) і = -1,...,А. Положим Я(Я) = {F Г _і(Я) : Tfc(F, Я) = 1} и заметим, что в силу леммы 1.1.4 множество Н{Н) является множеством правильно расположенных {к— 1)-мерных симплексов при к 1.
Два -мерных симплекса Si,S2 назовем смежными, если их пересечение является их общей (к — 1)-мерной гранью. Граф G (II) = (Я, F(Я)) с множеством вершин Я и множеством ребер Е(Н) = {{St,S2} СЯ : Si П S2 Є І\_і(,5і) П rfc_i(52)} назовем графом смежности множества fc-мерных симплексов II.
Триангуляцией J-мерпоп точечной конфигурации А называется такое множество Т(А) правильно расположенных Л-мерных симплексов с вершинами из /1, что объединение этих симплексов есть политоп [А]. При этом триангуляцией политопа называется триангуляция точечной конфигурации его вершин. Грани симплексов триангуляции назовем гранями триангуляции. Тогда при і = —l,0,...,d множество Г;(Т(/1)) \J\-i Г,(57) является множеством мерных граней триангуляции Т(А) — {Si,...,Si) и Г(Т(Л)) = UL-i 1\{Т(Л)) есть множество всех граней триангуляции Т(А).
Звездная развертка симплнциалыюго комплекса
Если в любой строке первый из разделителей является гранью каждого из следующих в ней (GT/1(L) Є Г(С?Т) для любого /І = 1,..., и для любого г = 7- ,...,7- +1 - 1, где т{Ь) = (ть...,т9) и тя+1 = t + 1), то развертку L назовем звездной.
Звездной разверткой триангуляции Т Т& назовем звездную развертку симплициального комплекса Г(Т) ее граней. Триангуляцию назовем звездно разворачиваемой, если она имеет звездную развертку. В разделе 3.1 построен пример разворачиваемой триангуляции 3-мерпого политопа, не имеющей звездной развертки.
Звездой star(F, С) = {F Є С : F С F }UT(F) грани F симплициального комплекса С назовем его подкомплекс, состоящий из всех граней комплекса С, содержащих F, и всех граней комплекса С, содержащихся в F. Положим Д0(/,) = Г(5,) и Д„() = Uj=V_1 Г(5 ) при n = 1,...,q. Следующее утверждение дает эквивалентное определение введенного понятия. Лемма 2.1.2 Развертка L = (Si:...,St) симплициалыюго комплекса С является звездной тогда и только тогда, когда выполняются равенства: Д„(і) = Дп_і() U8tar(GT„(),An()), n = 1,..., g, где T(L) = (7-1,...,7-,) и rq+1 = t + 1.
Доказательство. Пусть при n = l,...,g выполнено равенство An(L) = Д„_і(Л) U star(GTn(L), Дя()). Предположим, что развертка L не является звездной. Тогда существует такие ц Є {1,..., g} и г {г ,.. -,тд+1 — 1}, что Ст () Г(СТ). Тогда т г,, и GT(L) . Д _і(Ь), поскольку L является разверткой. Имеете с этим из равенства Дд() — A _i(-)Ustar(GT/,(i), Д (Л)) следует, что Полученное противоречие показывает неверность сделанного предположения. Поэтому развертка L является звездной.
Пусть развертка L = (Si,...,St) является звездной разверткой симплициалыюго комплекса С. Рассмотрим п Е {1,..., } и покажем, что An(L) = A„_i()Ustar(GT„(L), Дп(1)). Очевидно, что An„i(L)iJsUr(GTn(L), An(L)) С An(L). Покажем теперь выполнение обратного включения. Рассмотрим произвольную грань F Е An(L) н покажем, что F An„t(L) U star(GTn(/j), Д „(/,)). Для этого, очевидно, достаточно рассмотреть случаи F $ Д„_і(). Найдем такое минимальное г Е {т ,...,г/і+і — 1}, что F Е Г(5Т). Тогда GT{L) Е П/7), так как L является разверткой. Имеете с этим GTn(L) Є V(GT(L)), поскольку L является звездной разверткой. Таким образом, GTn(L) Є T{F) и, следовательно, F Є st&T(GTn(L),An(L)). Выполнение обратного включения показано. Лемма доказана.
Теперь становится почти очевидной следующая конкретизация леммы 2.1.1, которая потребуется в разделе 3.1.
Лемма 2.1.3 Пусть Gk{L) является последним нульмерным разделителем звездной развертки L = (S\,..., St) симплициального комплекса С. Если грань F Є Р(С) симплициалыюго комплекса С принадлежит единственной его гиперграни Sj и г Е Го ДГо )) то Gk{L) ф v.
Доказательство. Предположим, что Gk(L) = v. Тогда поскольку v Є Г0(,-) и L является разверткой, то к j. Так как Gk(L) явлпетсп последним нульмерным разделителем звездной развертки L, то Gk{L) Є V(Gj(L)). Грань F симплнциалыюго комплекса С принадлежит единственной его гиперграни Sj. Следовательно, F Є r(5})\(Ui=i (S,)). Тогда поскольку L является разверткой, то Gj(L) Є r(F). Таким образом, Gk(L) Є r(G,-(L)), G3{L) Є V(F) и, следовательно, v = Gk{L) Є I oUO, что противоречит условию леммы. Поэтому Gk(L) ф v- Лемма доказана.
В качестве примера рассмотрим плоскую (d = 2) точечную конфигурацию (см рис. 5) Л5 = {«і, «2,03,04,05}, где «і = (0,1), а2 (—2,0), «з = (2,0), ал = (0,3), а5 = (0,-1), и се триангуляцию 7 — { і,.92,5з,54}, где 5"і = [аі,а2,оз], S2 = К, 2, 4), - - [«і,«з,«4], #4 = [«2,03, «5] Последовательность симплексов Lx — {S2 S S S\) не является разверткой триангуляции Г, поскольку множество Г( )\(и?=2 (ST)) = {а5, [аг, яз], [«2,05], [«3,05], [«2,03,05]} не имеет единственного минималышго по включению элемента. Последовательности симплексов L2 = (Si,S2,S3,S4) и L3 = (S 1,5 2, 4,) являются развертками триангуляции Т с последовательностями разделителей G(L2) = (0,а4, [«3,04], а5), G{L3) = (0, «4,05,(03, 4]) ч т-векторами T(L2) = (2,4), T(L3) = (2,3) соответственно. Таким образом, поскольку аг, [«з, «ц], то L3 не является звездной разверткой триангуляции Г, в то время как L2 является таковой. Поэтому триангуляция Т является звездно разворачиваемой.
Развертка симплициального комплекса собственных граней симплициального политопа. Рассмотрим (/-мерный симплнциальный политоп М и покажем в соответствии с [35], каким образом может быть построена, в частности, развертка симплициального комплекса его собственных граней. Пусть v является такой внутренней точкой (/-мерного политопа М и с является таким вектором, что аффинные оболочки различных гиперграней политопа М пересекают прямую / = {v + ta : t Є 11} в различных точках. Тогда, если двигаться вдоль прямой I = {v -f ta : і Є R} из точки v в направлении, соответствующем вектору с, и далее, через бесконечность, возвратиться в точку v с другой стороны, то все гиперграни политопа М будут строго упорядочены в соответствии с моментами пересечения их аффинных оболочек при описанном движении вдоль прямой. Действительно, множество гпперграней Vd-i(M) политопа М упоря
Целочисленный пример неразворачиваемой триангуляции точечной конфигурации и следствие из пего
Покажем, что существует пример разворачиваемой триангуляции, не имеющем звездной развертки. Иолитопиалышм разбиением (/-мерного политопа M пазываетсп такое множество d-мсрных политопов V = {I\,... Pfi], вершины которых лвля-ютси вершинами политопа М, что их объединение совпадает с М, а пересечение любых двух из них пвлпетсп их общей гранью. Триангуляцией же политопа называется триангуляция точечной конфигурации его вершин. Положим А = [г?і,і з,і 4,и6,и7], Рг = [vi,v2,V4,v5,v7], / = [vuv2,v vb,v&]. Тогда Г3(Л) = {[vuvz,v4], [vuv4,v7], [иьі;6,У7], [ui,v3,v6], [щ,Щ,ъ7], [v3,v6,v7]}, 2( 2) = {[vi,ua,tn], [vuv4,v7], [VI,VB,VT], [vi,v2,vu], [v2,v4,v5], [v4,v5, v7]}, ІУРЗ) = {[vi,v2,v3], [vuv3,vG], [ui,u5,u6], [vuv2,vb], [v2,v3,v6], [v2,Vb,v6]}. Теперь заметим, что V = {Si, Pi, P2, Рз} является политопиальпым разбиением политопа [V7], а множества симплексов Ті = {S2,S3,SS}, Т2 — {S S Ss}, Т3 = {S6,S7,Si0} являются триангуляциямп политопов Рі,Р2,Рз соответственно. Поэтому T{V7) — { 1,-.-, 10} является триангуляцией точечной конфигурации V7 = {vi,...,v7}.
Теорема 3.1.1 Построенная в этом примере триангуляция T(V7) является разворачиваемой, по не является звездно разворачиваемой.
Покажем теперь, что триангуляция T{V7) не имеет звездной развертки. Предположим, что такая развертка L = (5,-,,... ,5,-10) существует. Пусть Gk{L) является ее последним нульмерным разделителем в последовательности разделителей G(L). Тогда Gk(L) Є {vi,.. ,,v7}.
Из леммы 2.1.3 следует, что: Gk(L) ф «і, так как симплекс S\ — \pi,v$,v,v7\ является единственным симплексом триангуляции T(V7), имеющим грань Fi = [г , , ]; Gk(L) ф v2,v7, так как симплекс Sa = [ 2, , 5, 7] является единственным симплексом триангуляции T(V7), имеющим грань F2 = [t 4,v5]; Gk{L) ф v3,v5, так как симплекс Si0 — [иг, іь, us» e] является единственным симплексом триангуляции T(V7), имеющим грань F3 = [v2,Ve\; Gk(L) ф vA,v&, так как симплекс , = [ 3, 4, , 7] является единственным симплексом триангуляции T(V7), имеющим грань РЛ = [v3,v7].
Таким образом, Gk{L) {vu... ,v7). Полученное противоречие ноказыва-ет неверность сделанного предположения. Теорема доказана.
Рассмотрим (/-мерную точечную конфигурацию А = [аі,...,ап] С Hd и такие вещественные числа Аі,...,Д„, что dim([/l ]) = d + 1, где а\ = (cti,\i), і — l,...,7t, 11 А = {а\,... ,« „}. Теперь рассмотрим множество Т + тех (/-мерных граней политопа [Л ], внутренняя нормаль к которым имеет положительную последнюю компоненту. Если все такие грани симплициальны, то Т+ — {[о,-,,... ,Qid+l] : Kv-jOi ] Є Т +} является триангуляцией точечной конфигурации Л и называется правильной (регулярной) триангуляцией (см., например, [3, 45, 54]). В [45] введено понятие слаборегулярной триангуляции: триангуляция Т (/-мерной точечной конфигурации Л называется слаборегулярной [45], если существует (/-мерная точечная конфигурация Л , имеющая регулярную триангуляцию Х% снмплициальный комплекс Г(Т ) граней которой изоморфен симплициалыюму комплексу Г(Г) граней триангуляции Т. Регулярные триангуляции, а следовательно, и слаборегулярные триангуляции являются разворачиваемыми (см., например, [45]).
В [45] предложен пример слаборегулярной триангуляции, не являющейся регулярной. Пример, рассмотренный в этом разделе, является его целочисленной модификацией. Вопросе связи понятий "слаборегулпрнап триангуляция" и "звездно разворачиваемая триангуляция" остается открытым, равно как и вопрос о связи понятий "регулярная триангуляция" и "звездно разворачиваемая триангуляция".
Целочисленный пример неразворачивасмой триангуляции точечной конфигурации и следствие из него.
М.Е. Rudin [48] построила пример (названный в [52] знаменитым) неразворачивасмой триангуляции точечной конфигурации, состоящей из вершин тетраэдра и еще восьми точек на его гранях. Эти дополнительные точки (точнее говоря, шесть из них) имели иррациональные барицентрические координаты. Таким образом оставалось неясным, существуют л и рациональные (или что то же — целочисленные) точечные конфигурации, допускающие нераз-ворачивасмые триангуляции. Приводимая здесь целочисленная модификация примера М.Е. Rudin даст положительный ответ на этот вопрос.
Рассмотрим триангуляцию Т(Л) Є Т[Л) произвольной (/-мерной точечной конфигурации Л и се развертку L = L(T(A)) = ( ,,...,5 ). Положим Ц = {S\,.. -,Si} при / = 1,.,., t. Тогда Gt(L), будучи минимальным по включению элементом множества Г(і;)\Г(І;_і), является /-ым разделителем развертки L, I = 1,..., L Из [44, 52] вытекает справедливость следующих двух утверж-дениґі. Положим /L (A) = Et-і //"Лі+1, где //" = ВД)І = UU Г,-(&), и і(А) = A (l + A)rf+1 , і = 0,...,(1. Тогда имеет место
Изучаемая триангуляция Т(Л) = {S5}\J{Si - і = 1)2,3,4, j Є {1,..., 11}\{5}}. To, что множество Т(Л) образует триангуляцию точечной конфигурации Л, может быть проверено непосредственно. Также нетрудно увидеть, что
Рассмотрим треугольник FQ = [Xi,X2,А 3]. Триангуляция Т(А) порождает триангуляцию точечной конфигурации F0 П Л, состоящую из 6 треугольников [X2,X3,Z2], [Аь A2,Z2], [А з,Уз,Яа], [XUY3,Z2], [АьГз, і], [А 3,П,/і], являющихся внешними 2-мерпыми гранями триангуляции Т(А) и принадлежащих соответственно симплексам S], S\, 5, 5f, Sf, Sl. Непосредственной проверкой (см. лемму 1.1.6) убеждаемся в том, что остальные 2-мерныс грани каждого из этих симплексов являются внутренними гранями Т(А). Так как аналогичные рассуждения справедливы и для остальных 2-мерных граней тетраэдра [A i,A 2, АГ3,А ], то каждым симплекс из множества Ті = {Sl,S?,Sf,Sf,Sf,Sj0 : і = 1,2,3,4} имеет одну внешнюю и три внутренние 2-мерпые грани триангуляции Т(А), а оставшиеся симплексы из Т2 = Т(А)\1\ — по четыре внутренние грани триангуляции Т(А).
Если предположить, что Sw Є 7 г, то Г( і)\Г(і4о) = {S41}, G4i(L) = S\\ и h\l{L) 1 по лемме 3.2.2, что противоречит утверждаемому леммой 3.2.2 равенству hf{L) = 0. Следовательно, S4i Є Ти Г(4і)\Г(40) = {F, 41}, где F есть 2-мерная грань тетраэдра S4i, явлпющапсп внешней 2-мер ной гранью триангуляции Т(Л), и G4i(L) — F. Тогда h l(L) 1 в силу леммы 3.2.2, что по лемме 3.2.1 противоречит тому, что /Г Л)(Л) = 0з,о(Л) + Ю0з,і(А) + ЗО0з,2(А). Из полученного противоречия следует, что для триангуляции Т(Л) развертки не существует. Теорема доказана.
Таким образом, триангуляция Т(А) является примером неразворачивае-мой триангуляции целочисленной точечной конфигурации А.
Покажем теперь, каким образом па основе произвольной неразворачнвае-мой триангуляции Т(А) (/-мерной точечной конфигурации A = {аі,...,а„} может бьіті построен пример такой триангуляции границы Т(Л ) некоторой ( 1 + 1)-мерной точечной конфигурации А = {а 0,..., а п}, что симплицналь-ньіґі комплекс V(Td(A )) ее граней не является изоморфным спмплициалыю-му комплексу собственных граней какого бы то ни было симплициального политопа. Для этого нам потребуется вытекающая из [35] (см. также [54, с. 241]) лемма.
Минимальные триангуляции трехмерных выпуклых многогранников из некоторых классов
При изучении триангуляции точечных конфигураций важное место занимает свойство разпорачнваемости, так как симплпциальный комплекс граней разворачиваемой триангуляции (триангуляции, допускающей определенное упорядочивание своих симплексов, называемое ее разверткой) обладает многими замечательными свойствами (см., например, [52]). М.Е. Rudm в [48] построила пример неразворачиваемой триангуляции точечной конфигурации, состоящей из вершин тетраэдра и еще восьми точек на его гранях. Таким образом, имеет смысл постановка задачи одновременного построения триангуляции н ее развертки. Более того, структура получаемых вторым ТФМ-алгоритмом триангуляции привела к задаче построения развертки триангуляции Т(А,І+І) таким образом, чтобы последовательность ее первых симплексов совпадала с построенной на предыдущем этапе разверткой триангуляции Т(Ап). Обобщение указанного свойства привело к введению понятия звездной развертки и постановке задачи ее построения.
Для политопа могут быть поставлены: задача нахождения минимально возможного числа симплексов в его триангулпциях и более общая задача описания множества всех /-векторов его триангуляции. Разумеется, эти задачи теоретически можно решить полным перебором всех триангуляции, однако, практически найти все триангуляции не представляется реальным уже в сколь-либо нетривиальных случаях. Волее того, A. Below, J.Л. De Ьоега и Л. Uicliter-Gcbert показали в [33], что задача определения для произвольного трехмерного политопа Л/, имеющего п вершин, и произвольного натурального числа к, существует ли триангуляция политопа М, содержащая не более к симплексов, является NP-полной. Таким образом, не известен полиномиальный но сложности алгоритм относительно числа вершин понзволь-ного 3-мерного политопа, строящий триангуляцию данного 3-мерного политопа, состоящую из минимально возможного числа тетраэдров. Ясно [33], что данная задача остается NP-полной, если вместо класса трехмерных политопов М рассматривается класс (/-мерных политопов, где d 3. Задача построения триангуляции (f-мерного куба, содержащей минимально возможное число и{ 1) симплексов, привлекает внимание исследователей (P.S. Мага [47], R.W. Cottle [37], J. Bohm [34], J.F. Sallce [49, 50], U.H. Hughes [40, 41, 42] Todd M.J., Tuncel L. [53]) споим приложением для аппроксимации неподвижных точек непрерывного отображении (И. Scarf [51], см. также обзор в [53]). Для нахождения v{d) при d — 4,5 используется линейное программирование (J.F. Sallee [49], R.B. Hughes [41]), дающее нижнюю оценку числа f(t/), и непосредственное построение триангуляции для того, чтобы показать ее неулучшаемость и тем самым решить задачу.
ІЇ диссертации теоретическим фундаментом дли исследования задач о нахождении минимально возможного числа симплексов в трпангуляциях политопа и об описании множества всех /-векторов его триангуляции служит полученный профессором В.II. Шевченко в [20] аналог уравнений Дсна-Соммервиля дли триангуляции, связывающий возможные значения компонент /-вектора триангуляции политопа и порождаемой ею триангуляции его границы. Естественная схема решении данных задач состоит в том, чтобы с помощью алгоритмов триангуляции сгенерировать триангуляции, соответствующие всему возможному спектру значений исследуемой характеристики, и доказать, что других значений данная характеристика иметь не может. При этом следует заметить, что исследование свойств триангуляции политопа и составляющих их симплексов позволяет организовать процесс генерации триангуляции более целенаправленно.
Цель работы. Создание модификаций алгоритма Фурьс-Моцкпна для: построения триангуляции точечной конфигурации, построения триангуляции и ее развертки для точечной конфигурации, построении триангуляции и се звездной развертки для точечной конфигурации. Получение оценок временной сложности разрабатываемых алгоритмов и исследование их свойств. Применение разрабатываемых алгоритмов для решения задач об описании миоліества /-векторов триангуляции 4-мерного куба, об описании /-векторов триангуляции границы 5-мерного куба, о нахождении минимального числа тетраэдров в триангуляцппх трехмерных политопов из некоторых классов.
Научная новизна. Создана модификация алгоритма Фурьс-Ыоцкипа (КТФМ-алгоритм) дли построения триангуляции, триангуляции границы точечной конфигурации и описывающей ее неприводимой системы неравенств. Исследованы свойства КТФМ-алгоритма и получаемых им триангуляции. Показана оптимальность КТФМ-алгоритма п пространствах нечетной размерности среди решающих эти задачи алгоритмом, обладающим свойством открытости. При этом входом считается точечная конфигурация пространства Kd, первые (/ + 1) точки которой аффинно независимы.
Создана модификация алгоритма Фурье-Моцкнпа (КРТФМ-алгоритм) для построения триангуляции и ее развертки для точечной конфигурации. Введено понятие звездной развертки триангуляции и построен пример триангуляции точечной конфигурации, имеющей развертку, но не имеющей звездной развертки. Показано, что КРТФМ-алгоритм в нскомбинироваппом режиме (ЗРТФМ-алгоритм) строит триангуляцию и ее звездную развертку для точечной конфигурации.