Триангуляции выпуклых многогранников тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Груздев, Дмитрий Валентинович

• Груздев, Дмитрий Валентинович
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Груздев, Дмитрий Валентинович

Введение.

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-мерного куба. 13G

Введение диссертации (часть автореферата) на тему «Триангуляции выпуклых многогранников»

Общая характеристика работы

Актуальность работы. К построению и исследованию триангуляции точечных конфигураций и выпуклых многогранников, являющихся выпуклыми оболочками конечного множества точек и называемых также политопами, приводят, в частности, задачи, возникающие в следующих областях: вычислительной геометрии, теории выпуклых многогранников, целочисленного линейного программирования. Триангуляция выпуклого многогранника является правильным (грань-в-грань) его разбиением на симплексы и используется, например, для нахождения числа целочисленных точек выпуклого многогранника и точного вычисления его объема.

Фундаментальный факт теории линейных неравенств — теорема Минковского-Нейля — утверждает, что множество М С Rd является политопом тогда и только тогда, когда М совпадает с множеством решений некоторой конечной системы линейных неравенств и ограничено, причем если М является J-мерным политопом, то такой системой является система неравенств, соответствующих гиперграням политопа М (при этом данная система оказывается неприводимой). Для перехода от одного описания политопа к другому в разное время было предложено несколько алгоритмов. Одним из них и, по всей вероятности, первым по времени создания является алгоритм Минковского, требующий для начала работы всего входного описания политопа и непосредственно следующий из теоремы Минковского-Вейля. Другим алгоритмом является алгоритм Фурье-Моцкина, основная идея которого, восходящая к Фурье и развитая Моцкиным, выражена в методе двойного описания [15, 36] (см. также [18]) и методе "под-над" [17, 39]. Пусть (/-мерный политои М задан выпуклой оболочкой конечного множества точек Л — {«i,.,ajv} С Алгоритм Минковского для каждого аффинно независимого (/-элементного подмножества А' С А, по одну сторону аффинной оболочки которого располагаются все точки множества Л, получает неравенство, задающее соответствующее полупространство. Полученная система неравенств является выходом алгоритма Минковского, который, таким образом, имеет временную сложность 0(Nd). В то же время алгоритм Фурье-Моцкина, являясь итерационным, на каждой итерации получает очередную точку множества А и строит систему неравенств, описывающую выпуклую оболочку полученного множества точек, что позволяет оценить временную сложность его модификации (метод "под-над") величиной

Большое внимание, начиная с работы [3], уделяется изучению так называемых правильных (регулярных) триангуляций и разбиений, находящих приложения в теории дифференциальных уравнений. Для их построения приходится находить вупуклую оболочку множества точек в пространстве на единицу большей размерности. Таким же образом может быть построена и триангуляция Делоне [11], имеющая большое значение, например, для решения задачи о нахождении ближайших точек из некоторого конечного множества. Работа в пространстве на единицу большей увеличивает временную сложность алгоритмов. Поэтому другие способы построения триангуляции, работающие в исходном пространстве, также имеет смысл изучить тем более, что они допускают эффективные реализации (см. главу 1), полезные модификации (см. главу 2) и позволяют решать ряд задач (см. главу 4).

Диссертация является развитием идей и подходов к построению триангуляций, которые были рассмотрены и получили свое обоснование, например, в работах П.II. Шевченко [19, 20], C.W. Lee [45]. Данные идеи требовали создания реализующих и комбинирующих их эффективных алгоритмов построения триангуляции. Цель была достигнута созданием указанных алгоритмов как модификаций алгоритма Фурье-Моцкина. Таким образом был создан КТФМ-алгоритм (комбинированный алгоритм Фурье-Моцкина для построения триангуляции) и его частные случаи: первый ТФМ-алгоритм и второй ТФМ-алгоритм.

Особый интерес при этом представляет гипотеза профессора В.II. Шевченко, согласно которой каждый /-вектор из множества /-векторов триангуляций (-/-мерных политопов достигается на триангуляципх, получаемых вторым 'ГФМ-алгоритмом. Второй ТФМ-алгоритм является итерационным и, построив на предыдущем этапе триангуляцию Т(Ап) уже рассмотренного множества точек Лп = {ai,.,an}, при получении очередной точки an+i дополняет уже построенную триангуляцию новыми симплексами до триангуляции всего множества полученных точек T(An+i) = T(An)\JTn. При этом триангуляцией конечного множества точек (точечной конфигурации) А является правильное разбиение его выпуклой оболочки на симплексы с вершинами из А.

При изучении триангуляций точечных конфигураций важное место занимает свойство разворачиваемости, так как симплициальный комплекс граней разворачиваемой триангуляции (триангуляции, допускающей определенное упорядочивание своих симплексов, называемое ее разверткой) обладает многими замечательными свойствами (см., например, [52]). М.Е. Rudin в [48] построила пример неразворачиваемой триангуляции точечной конфигурации, состоящей из вершин тетраэдра и еще восьми точек на его гранях. Таким образом, имеет смысл постановка задачи одновременного построения триангуляции и ее развертки. Более того, структура получаемых вторым ТФМ-алгоритмом триангуляций привела к задаче построения развертки триангуляции T(An+i) таким образом, чтобы последовательность ее первых симплексов совпадала с построенной на предыдущем этапе разверткой триангуляции Т(Ап). Обобщение указанного свойства привело к введению понятия звездной развертки и постановке задачи ее построения.

Для политопа могут быть поставлены: задача нахождения минимально возможного числа симплексов в его триангуляциях и более общая задача описания множества всех /-векторов его триангуляций. Разумеется, эти задачи теоретически можно решить полным перебором всех триангуляций, однако, практически найти все триангуляции не представляется реальным уже в сколь-либо нетривиальных случаях. Колее того, A. Below, J.A. De Loera и J. Richter-Gebert показали в [33], что задача определения для произвольного трехмерного политопа М, имеющего п вершин, и произвольного натурального числа к, существует ли триангуляция политопа М, содержащая не более к симплексов, является NP-полной. Таким образом, не известен полиномиальный но сложности алгоритм относительно числа вершин поизволь-ного 3-мерного политопа, строящий триангуляцию данного 3-мерного политопа, состоящую из минимально возможного числа тетраэдров. Ясно [33], что данная задача остается NP-полной, если вместо класса трехмерных политопов М рассматривается класс (/-мерных политопов, где d > 3. Задача построения триангуляции rf-мерного куба, содержащей минимально возможное число u{d) симплексов, привлекает внимание исследователей (P.S. Мага [47], R.W. Cottle [37], J. Bohm [34], J.F. Sallee [49, 50], R.B. Hughes [40, 41, 42] Todd M.J., Tuncel L. [53]) своим приложением для аппроксимации неподвижных точек непрерывного отображения (Н. Scarf [51], см. также обзор в [53]). Для нахождения i/(d) при d = 4,5 используется линейное программирование (J.F. Sallee [49], R.B. Hughes [41]), дающее нижнюю оценку числа v(d), и непосредственное построение триангуляции для того, чтобы показать ее неулучшаемость и тем самым решить задачу.

В диссертации теоретическим фундаментом для исследования задач о нахождении минимально возможного числа симплексов в триангуллциях политопа и об описании множества всех /-векторов его триангуляций служит полученный профессором В.II. Шевченко в [20] аналог уравнений Дена-Соммервиля для триангуляций, связывающий возможные значения компонент /-вектора триангуляции политопа и порождаемой ею триангуляции его границы. Естественная схема решения данных задач состоит в том, чтобы с помощью алгоритмов триангуляции сгенерировать триангуляции, соответствующие всему возможному спектру значений исследуемой характеристики, и доказать, что других значений данная характеристика иметь не может. При этом следует заметить, что исследование свойств триангуляций политопа и составляющих их симплексов позволяет организовать процесс генерации триангуляций более целенаправленно.

Цель работы. Создание модификаций алгоритма Фурье-Моцкина для: построения триангуляции точечной конфигурации, построения триангуляции и ее развертки для точечной конфигурации, построения триангуляции и ее звездной развертки для точечной конфигурации.

Получение оценок временной сложности разрабатываемых алгоритмов и исследование их свойств.

Применение разрабатываемых алгоритмов для решения задач об описании множества /-векторов триангуляций 4-мерного куба, об описании /-векторов триангуляции границы 5-мерного куба, о нахождении минимального числа тетраэдров в триангуляциях трехмерных политопов из некоторых классов.

Научная новизна. Создана модификация алгоритма Фурье-Моцкина (КТФМ-алгоритм) для построения триангуляции, триангуляции границы точечной конфигурации и описывающей ее неприводимой системы неравенств. Исследованы свойства КТФМ-алгоритма и получаемых им триангуляций. Показана оптимальность КТФМ-алгоритма в пространствах нечетной размерности среди решающих эти задачи алгоритмом, обладающим свойством открытости. При этом входом считается точечная конфигурация пространства первые (с/ + 1) точки которой аффинно независимы.

Создана модификация алгоритма Фурье-Моцкина (КРТФМ-алгоритм) для построения триангуляции и ее развертки для точечной конфигурации. Введено понятие звездной развертки триангуляции и построен пример триангуляции точечной конфигурации, имеющей развертку, но не имеющей звездной развертки. Показано, что КРТФМ-алгоритм в некомбинированном режиме (ЗРТФМ-алгоритм) строит триангуляцию и ее звездную развертку для точечной конфигурации.

Получены оценки временной сложности разработанных алгоритмов.

С использованием КТФМ-алгоритма для построения триангуляций решены задачи об описании множества /-векторов триангуляций 4-мерного куба, об описании /-векторов триангуляций границы 5-мерного куба, о нахождении минимального числа тетраэдров в триангуляциях трехмерных политопов из некоторых классов.

Методы исследования. Используется аппарат теории выпуклых многогранников, вычислительной геометрии, анализа и разработки алгоритмов.

Научная и практическая ценность. Разработанные алгоритмы

КТФМ-алгоритм и КРТФМ-алгоритм) могут быть использованы длп эффективного построения триангуляций, их разверток и звездных разверток для точечных конфигураций.

С помощью КТФМ-алгоритма были построены: триангуляции 4-мерного куба, покрывающие весь спектр /-векторов триангуляций 4-мерного куба, триангуляции границы 5-мерного куба, покрывающие весь спектр /-векторов триангуляций границы 5-мерного куба, триангуляции трехмерных политопов из некоторых классов, содержащие минимально возможное число тетраэдров.

Апробация работы и публикации. Основные результаты работы докладывались и обсуждались на научных семинарах кафедры математической логики и высшей алгебры (рук. проф. В.Н. Шевченко) Нижегородского госуниверситета и на следующих конференциях: первая и четвертая молодежные научные школы по дискретной математике и ее приложениям (Москва,1997 г., 2000 г.), конференция "Вычислительная математика и кибернетика 2000", посвященная 80-летию Ю.И. Неймарка (Н.Новгород, 2000 г.), VII Международный семинар "Дискретная математика и ее приложения" (Москва, 2001 г.), XI Межгосударственная школа-семинар "Синтез и сложность управляющих систем" (Н.Новгород, 2001 г.), XIII Международная конференция "Проблемы теоретической кибернетики" (Казань, 2002 г.), Российская конференция "Дискретный анализ и исследование операций" (Новосибирск, 2002 г.), XIII и XIV Международные школы-семинары "Синтез и сложность управляющих систем" (Пенза, 2002 г., Н.Новгород, 2003 г.), XII Всероссийская конференция "Математическое программирование и приложения" (Екатеринбург, 2003 г.),

Работа выполнена при поддержке РФФИ (код проекта 05-01-00552-а), Министерства образования РФ (СПбКЦ, гранты А03-2.8-475 и А04-2.8-893). Результаты работы отмечены стипендиями Правительства Российской Федерации и стипендиями администрации Нижегородской области имени академика Г.А. Разуваева.

По теме диссертации опубликовано 15 работ.

Автор благодарит научного руководителя доктора физико-математических наук, профессора В.П. Шевченко за постановку задач и руководство работой.

Рассмотрим теперь две идеи построения триангуляции точечной конфигурации Л = {ах,.,адг} С Rd, выпуклая оболочка [Л] которой является «/-мерным политопом. (Все используемые здесь понятия и обозначения вводятся в разделе 1.1.)

Первая идея по-существу следует из [32, с. 624]: выбрать точку аг-, являющуюся вершиной политопа [Л] и построить по индукции триангуляции T(F П /1) 6 T{F П /1) точечных конфигураций F Г) Л для всех не содержащих а,- гиперграней F G ([Л]) политопа [Л] так, чтобы все построенные (d— 1)-мерные симплексы образовывали множество правильно (грань-в-грань) расположенных симплексов, обозначаемое через Н+. Тогда множество Т(А) = {[a,, 51] : S Е Н+} будет триангуляцией точечной конфигурации А.

Вторая идея (см. например, [19, 20]) заключается в том, чтобы выбрать точку а,- £ А и построить по индукции триангуляцию Т(А') точечной конфигурации А' = Л\{аг}, при этом будем считать, что выпуклая оболочка [А'] является J-мерным политопом. После этого следует образовать множество Н~ из таких (d— 1)-мерных граней симплексов триангуляции Т(А'), лежащих на границе политопа [А'], аффинная оболочка каждой из которых отделяет точку а{ от политопа [А'}. Тогда множество Т(А) = Т(Л') U {[а,-,^] : S G Н~} будет триангуляцией точечной конфигурации А.

Разработанный КТФМ-алгоритм (см. раздел 1.2), комбинируя эти идеи, является эффективным их воплощением. При этом точки точечной конфигурации А = {ai,.,ajv} рассматриваются последовательно и требуется только, чтобы выпуклая оболочка первых (d + 1) точек являлась J-мерным симплексом. КТФМ-алгоритм наряду с триангуляцией Т(А) точечной конфигурации А строит и порождаемую ею триангуляцию II границы точечной конфигурации А, состоящую из (d— 1)-мерных граней симплексов триангуляции Т(А), лежащих на границе политопа [Л]. КТФМ-алгоритм также строит неприводимую систему неравенств, описыающую политоп [Л].

Содержание диссертации

13 главе 1 разрабатывается модификация алгоритма Фурье-Моцкина для построения триангуляции точечной конфигурации (КТФМ-алгоритм).

Н разделе 1.1 приведены основные определения и свойства, используемые в главе 1. Выпуклую оболочку и аффинную оболочку множества точек Л С Rd' обозначим через [Л] и afT(yl) соответственно. Через Г,-(Л/) обозначим множество г-мерных граней выпуклого многогранника М С Rd' размерности сПш(Л/) = d, являющегося выпуклой оболочкой конечного множества точек и называемого далее (/-мерным политопом, i = —1 ,.,</. Здесь Г1 (Л/) = {0} и ГДД/) = {Л/}. Положим Г(Л/) = U?=i П(Л/). Если |Г0(Л/)| = d + 1, то «/-мерный политоп Л/ будем называть d-мерным симплексом.

Конечное множество точек А = {а1,.,ап} С Rd', выпуклая оболочка [Л] точек которой является (/-мерным политопом, назовем d-мерпой точечной конфигурацией. Если порядок точек в множестве Л зафиксировать, то соответствующую последовательность точек будем обозначать через Л = («1,. ,ап). Множество всех (/-мерных точечных конфигураций пространства Rd обозначим через Ad = {А С Rd : |Л| < +оо, с1'ип([Л]) = (/}. Положим Ad = {(at,. ,а„) : ai,.,an G Rd, dim([ai,., arf+1]) = d, n > d+ 1}.

Пусть (/-мерный политоп M = [Л], где Л G Ad- Если х = (xi,.,xd) G Rd и b = (b0,bi,.,bd) G Rd+1, то положим х = (1,^1,., xj) и (b, х) = bo + bixi + . + bjxd■ Если (d — 1)-мерный политоп F лежит в какой-либо гиперграни (/-мерного политопа М = [А] С Rd, то через bp — bj/ обозначим такой вектор из Rd+1, что (б£,х) = 0 при любом х G F и (Ь^,х) > 0 при любом х G [Л]. Тогда из теоремы Минковского-Нейля (см., например, [2,12]) следует, что политоп [Л] = { х G Rd : Vi*1 G Г<г1([Л]) {bp, х) > 0 } описывается неприводимой системой неравенств {(Ьр,х) > О, F G ([Л])}.

Гипергранями симплициального комплекса С размерности d = dim(C) называются его грани (симплексы из С) размерности d. Симилициальные комплексы С\ и С2 называются изоморфными, если между ними можно установить биекцию, сохраняющую отношение включения.

Симплексы, составляющие некоторое конечное множество, расположены правильно (грань-в-грань) [16, с. 24], если пересечение любых двух симплексов является их общей гранью. Если Н является конечным множеством правильно расположенных fc-мерных симплексов, то при i = —1,0,.,А; множество Г;(#) = Use// ГД^) назовем множеством i-мерных граней множества симплексов // и положим Г(#) = U*=i Г,-(//) = Use//r(5).

Триангуляцией «/-мерной точечной конфигурации А называется такое множество Т(А) правильно расположенных «/-мерных симплексов с вершинами из А, что объединение данных симплексов есть политоп [/1]. При этом триангуляцией политопа называется триангуляция точечной конфигурации его вершин. Гиперграпями триангуляции Т(А) назовем ее («/ — 1)-мерные грани. Грань триангуляции Т(А) назовем внутренней, если она имеет внутреннюю точку политопа [Л] в afT(Л), в противном случае назовем ее внешней. Внутренняя гипергрань триангуляции Т(А) является гранью ровно двух симплексов из 7'(Л), в то время как внешняя гипергрань триангуляции Т(Л) является гранью единственного симплекса из Т(Л) (см., например, [20]). Множество внешних гиперграней триангуляции Т(А) обозначим через Н(Т(А)). Множество всех триангуляций точечной конфигурации А обозначим через Т(Л), а множество всех триангуляций «/-мерных точечных конфигураций обозначим через Td■

Множество правильно расположенных (d — 1)-мерных симплексов Та(Л) называется триангуляцией границы (д-триангуляцией) «/-мерной точечной конфигурации Л, если для каждой гиперграни F £ IYi([Л]) существует такая триангуляция T(F П А) <Е T(F П Л), что Тд(А) = UFerd,(H]) T{F П Л). При этом триангуляцией границы (д-триангуляцией) политопа называется триангуляция границы точечной конфигурации его вершин. Множество всех триангуляций границы точечной конфигурации А обозначим через Тд(А). Заметим, что триангуляция Т(Л) точечной конфигурации Л порождает ее ^-триангуляцию Н(Т(А)) G Тд{А).

В разделе 1.2 кратко излагаются и иллюстрируются алгоритм Фурье

Моцкина и его предлагаемая модификация.

В разделе 1.3 описывается предлагаемый КТФМ-алгоритм (комбинированный алгоритмом Фурье-Моцкина для построения триангуляции точечной конфигурации), названный таким образом, поскольку точки входной точечной конфигурации обрабатывает последовательно и каждую точку может обрабатывать в режиме либо первого, либо второго ТФМ-алгоритма. Размерность d при получении оценок временной сложности алгоритмов здесь и далее считается константой. КТФМ-алгоритм решает следующие задачи.

Задача 31 (Ad) (Задача построения триангуляции). Дана последовательность точек (а!,.,адг) £ Ad- Требуется построить триангуляцию точечной конфигурации {аь., адг}, организовав последовательную обработку точек таким образом, чтобы при п = d+1,., N после обработки точки ап имелась триангуляция точечной конфигурации {ai:. ,ап}.

Задача 32(Ad) (Задача построения ^-триангуляции). Дана последовательность точек (ai,.,адг) £ Ad- Требуется построить триангуляцию границы точечной конфигурации {ai,., адг}, организовав последовательную обработку точек таким образом, чтобы при п = d + 1,., N после обработки точки ап имелась триангуляция границы точечной конфигурации {ai,.,an}.

Задача 33(Ad) (Задача построения неприводимой системы неравенств, описывающих выпуклую оболочку). Дана последовательность точек (аь. ,адг) £ Ad- Требуется построить неприводимую систему неравенств, описывающую политоп [аь ., адг], организовав последовательную обработку точек таким образом, чтобы при п — d+ 1,., N после обработки точки ап имелась неприводимая система неравенств, описывающая политоп [«1,. ,ап].

На вход КТФМ-алгоритма подается произвольная (/-мерная точечная конфигурация Лдг, заданная последовательностью своих точек Лдг = (ai,.,aN) £ Ad, и вектор uN = (ud+2, - - -, uN) £ {-1, +l}iV"d-1. Положим An = {ai,. .,«„}, An = («1, • • • ,«n) и un = (ud+2,-.,un) при n - d+ 1,., N.

КТФМ-алгоритм вначале полагает T(Ad+\) = {[Д^-ц]}, Hd+1 =

IViQ/ld+i]) = H(T(Ad+i)) и, найдя неприводимую систему неравенств {(bd+i,i,x) > 0, i = 1,. (здесь m<i+i =d+ 1), описывающую политоп

Ad+1], далее при п = d+l,.,N — 1 по триангуляции Т(Ап), триангуляции границы //„ точечной конфигурации Ап и точке an+J КТФМ-алгоритм находит триангуляцию Т(Лп+1) и триангуляцию границы IIn+1 = ll(T(An+1)) точечной конфигурации An+i следующим образом: разбить Нп на Я" = {F £ //„ : (ЬАрп,а^.й) < 0}, Я„° = {F 6 //„ : (14п,^Т) = 0} и К = £ Я» : > 0}; если Н~ = 0 (an+i £ [Л„]), то положить Т(Лп+1) = Т(Л„), //„+i = //„ и закончить (остановить) итерацию; если ип+1 = +1 (режим первого ТФМ-алгоритма), то построить триангуляцию Т(Ап+1) = {[F+,an+1] : F+ £ //+} и триангуляцию границы Нп+1 = //+U{[FnF"'°,an+1] : F £ //+, F"-° £ //" U Я°, dim(FnF"-0) = d- 2}; если же un+i = —1 (режим второго ТФМ-алгоритма), то построить триангуляцию Т(Ап+1) = Т(Ап) U {[F",an+i] : F~ £ Я~} и триангуляцию границы Яп+1 = Я+ U Я° U {[F П F",an+1] : F £ Я+ U Я°, F" £ Я", dim(FnF-) = d -2}; найти неприводимую систему неравенств {(6n+it,-, ж) >0, i = 1,. ,m„+i}, описывающую политоп

И»+1].

В разделе 1.4 изучаются свойства КТФМ-алгоритма. Установлен изоморфизм симплициального комплекса граней получаемой КТФМ-алгоритмом триангуляции границы точечной конфигурации симпли-циальному комплексу собственных граней некоторого симплициального политопа.

На основе этого факта и теоремы о верхней границе (см., например, [12, 54]) получена оценка временной сложности КТФМ-алгоритма. Теорема 1.4.7 утверждает, что КТФМ-алгоритм решает задачи 31(Д*), 32(Аг), 33(Ad) " строит триангуляцию Т(Лдг) = CTFMj(An,un) £ Т(Лдг), порождаемую ею триангуляцию границы IIN = Н(Т(А^)) = СТFMq(An,un) £ Тд(Ан) точечной конфигурации Лдг, заданной последовательностью своих точек An = (ai,.,ajv) G Аь и неприводимую систему неравенств {{l>N,i,x) > 0, i = 1,. ,mjv}, описывающую политоп [Адг], с временной сложностью 0(N^+1).

Устанавливается оптимальность КТФМ-алгоритма в пространствах нечетной размерности среди алгоритмов, обладающих свойством открытости.

Теорема 1.4.8. КТФМ-алгоритм при нечетном d является оптимальным для решения задач 31 (Ad), 32(Ad) и 3Z(Ad).

КТФМ-алгоритм, на каждой своей итерации работающий в режиме первого ТФМ-алгоритма, называется первым ТФМ-алгоритмом. КТФМ-алгоритм, на каждой своей итерации работающий в режиме второго ТФМ-алгоритма, называется вторым ТФМ-алгоритмом. Положим A'd = {(аь., ап) £ Ad а,- [ai,.,a,-i], i G {d + 2,., n} }.

Теорема 1.4.9. Второй ТФМ-алгоритм обрабатывает произвольную точечную конфигурацию An, заданную последовательностью своих гпоче/t An — (а!,.,адг) G A'd, с временной сложностью 0(N\T(An)\), не превосходящей

0(\T(An)\2).

Установлено, что первый ТФМ-алгоритм может быть использован для нахождения крайних точек точечной конфигурации An, заданной последовательностью своих точек An = (ai,.,ajv) £ Ad- Теорема 1.4.10 показывает, что первый ТФМ-алгоритм, применяемый к An, строит триангуляцию T(An) и ^-триангуляцию //дг таким образом, что Г0(T(An)) = го(^лг) = Го ([An]).

Замечено, что нижние оценки числа симплексов в получаемых КТФМ-алгоритмом, первым и вторым ТФМ-алгоритмами триангуляциях и d-триангуляциях произвольных «/-мерных точечных конфигураций тривиальны, поскольку все точки точечной конфигурации могут принадлежать выпуклой оболочке ее первых (d + 1) точек. Получены верхние оценки числа симплексов в триангуляциях, строимых КТФМ-алгоритмом, первым и вторым ТФМ-алгоритмами. Через fij,(d,N), /.ij(d,N), fij(d,N) обозначим максимальное количество симплексов в триангуляциях, получаемых соответственно КТФМ-алгоритмом, первым ТФМ-алгоритмом и вторым ТФМалгоритмом для (/-мерных точечных конфигураций, состоящих из N точек. А через n°(d,N), fil(d,N), fil(d,N) обозначим максимальное количество симплексов в д-триангуляциях, получаемых соответственно КТФМ-алгоритмом, первым ТФМ-алгоритмом и вторым ТФМ-алгоритмом для (/-мерных точечных конфигураций, состоящих из N точек.

Теорема 1.4.11. Пусть 8 = [d/2 J и N >d+ 1. Тогда при к = 0,1,2

4(4N) = fr-xMi]) = J 5) для d = 28, tikd{d,N) = fd-i{[CdN]) = 2^N ~ * ~ ^ для d=25+l.

Теорема 1.4.13. Пусть 5 = [d/2\ и N > d + 1. Тогда

5 ~ 2) - ~ 2 ~8 ~1)~d dM d = 25+L

Теорема 1.4.14. Пусть 8 = [d/2\ и N > d+ 1. Тогда

N ~5 ~ ^ - N) ~ iV) - 2 8 " d ~ 1 dM d = '15, ~ *) < /4(4 N) < /4((/, N) < -d- 1 And = 26 + 1.

Основные результаты главы 1 опубликованы в работах [8, 9,10, 20, 27, 29].

В главе 2 разрабатывается модификация алгоритма Фурье-Моцкина для построения триангуляции и ее развертки для точечной конфигурации (КРТФМ-алгоритм).

В разделе 2.1 приводятся основные определения и свойства, используемые во второй главе.

Разверткой симплициального комплекса С называется такая последовательность его гиперграней L = (Si,., St), что при I = 1 ,.,< множество r(5'i)\(Ur=1i Г'С'З'т)) имеет единственный минимальный по включению элемент, называемый l-ьт разделителем развертки L и обозначаемый через Gi(L). Через t(L) — (ti,.,t9) обозначим вектор, в котором т\,.,тч являются упорядоченными по возрастанию номерами нульмерных разделителей развертки L. Заметим, что q = |Г0(С)| — dim(C) — 1. Если GTtx(L) 6 Г((7Г) для любого /< = 1,.,<7 и для любого г = 1 — 1, где т(Ь) = (ri,.,r9) и т9+1 = t + 1, то развертку L назовем звездной. Множество star(F, С) = {F' Е С : F С F'} U Г(F) называется звездой грани F симплициального комплекса С. Положим Д0(L) = ВД) и An(L) = U^V"1 Г(5,-) при п = 1,., q.

Лемма 2.1.2. Развертка L = (Si,.,St) симплициального комплекса С является звездной тогда и только тогда, когда выполняются равенства: An{L) = An-i(L) U star(GTn(L), An(L)), п = 1,.,q, где r{L) = (п,.,rq) и

Tq+i = t + 1.

Разверткой и звездной разверткой триангуляции Т ETd назовем соответственно развертку и звездную развертку симплициального комплекса Г(Т) ее граней. Триангуляцию назовем разворачиваемой и назовем ее звездно разворачиваемой, если она имеет развертку и звездную развертку соответственно.

В разделе 2.2 представлена практическая реализация следующего из работы II. Bruggesser и P. Mani [35] (см. также [54]) алгоритма построения развертки комплекса собственных граней симплициального политопа.

В разделе 2.3 вводится отношение предшествия -<„ на получаемой КТФМ-алгоритмом d-триангуляци IIn = {Fu.,Fm} = CTFMd(An,nn) точечной конфигурации Ап, где Ап = {a,i,.,an}, ип = (ud+2,.,un), An = (ai,.,ayv) G Аи uN = (ud+2,. ,uN) £ {+1,-l}^"1 N - 1 > n > d + 1 и an+i ^ [ai,., an], таким образом, что по следствию 2.3.3 теоремы 2.3.2 в случае un+i = -1,если II~ = {Fi,., Fp} и Fk -<„ Fk+l при k = 1,. то последовательность симплексов (F\,.,FP) является разверткой симплициального комплекса Г(//"); а в случае ип+1 = +1, если //+ = {Fq,.,Fm} и Fk -<п Fk+i при к — q,. ,m — 1, то последовательность симплексов

Fm,., Fq) является разверткой симплициального комплекса Г(#+).

В разделе 2.4 описывается предлагаемый КРТФМ-алгоритм (комбинированный алгоритм Фурье-Моцкина для построения триангуляции и ее развертки для точечной конфигурации), модифицирующий КТФМ-алгоритм таким образом, чтобы вместе с триангуляцией строилась и ее развертка. КРТФМ-алгоритм решает следующую задачу.

Задача 34(Ad) (Задача построения триангуляции и ее развертки). Дана последовательность точек (аь.,адг) £ Ad. Требуется построить триангуляцию и ее развертку для точечной конфигурации {аь. ,адг}5 организовав последовательную обработку точек таким образом, чтобы при п = d+1,. ,N после обработки точки ап имелась триангуляция и ее развертка для точечной конфигурации {аь., ап}.

На вход КРТФМ-алгоритма подается произвольная (/-мерная точечная конфигурация Лдг, заданная последовательностью своих точек Лдг = (ai,., алг) £ Ad, и вектор uN = (ud+2, • • •, un) € {-1, +l}Ar-d-1. Положим Ап = {ai,. ,ап}, An = (au.,an) и un = (ud+2,., un) при n = d+ 1,., N.

КРТФМ-алгоритм вначале полагает T(Ad+i) = {[Л^+i]}, Ld+i = ([Л<т])? Hd+1 = II(T(Ad+1)) = F([/l(i+i]) и далее последовательно при n = d+1,., N— 1 производит следующие действия: разбить Un на II~ = {F £ IIn : (ЬАР"< 0}, 11° = {F £ IIп : 0} и //+ = {F £ IIn : (ЪАр\а^Ц) > 0}; если //" = 0 (an+i £ [Л„]), то положить T(An+l) = Т(Ап), Ln+1 = Ln и IIn+1 = Нп', в ином случае, применяя итерацию КТФМ-алгоритма, построить Г(Ап+1) = CTFi\lT(An+l,un+l) и Iln+i = CTFMd(An+l,un+1)-, если ип+1 = +1 (режим первого РТФМ-алгоритма), то упорядочить симплексы из //+ по отношению предшествия -<п так, что Fk <п Fk+i при к = 1,.,/>+ - 1 и //+ = {Fi,., Fp+}, после чего положить L„+1 = ([Fp+,an+1],.,[F1,rtn+1]); если же un+l = —1 (режим второго РТФМ-алгоритма), то упорядочить симплексы из Н~ по отношению предшествия -<п так, что Fk -<п Fk+i при к = 1,.,р — 1 и //„ = {Fi,.,Fp-}, после чего положить Ln+1 = (Ln, [Fi,an+i],., [Fp, an+i]).

Теорема 2.4.2. КРТФМ-алгоритм решает задачу 34(Ad) и строит разворачиваемую триангуляцию T(An) и ее развертку Ln для точечной конфигурации А^, заданной последовательностью своих точек An = (ai,. . ,a;v) G Ad, с временной сложностью log N).

В разделе 2.5 рассматривается КРТФМ-алгоритм на каждой своей итерации работающий в режиме второго РТФМ-алгоритма и называемый ЗРТФМ-алгоритмом, поскольку он решает следующую задачу.

Задача 35 (Ad) (Задача построения триангуляции и ее звездной развертки). Дана последовательность точек (ai,.,a^) G Ad- Требуется построить триангуляцию и ее звездную развертку для точечной конфигурации {ai,. организовав последовательную обработку точек таким образом, чтобы при п = d+ 1,., N после обработки точки ап имелась триангуляция и ее звездная развертка для точечной конфигурации {аь. ,ап}.

Теорема 2.5.1. ЗРТФМ-алгоритм решает задачу 35 (Ad) и строит звездно разворачиваемую триангуляцию Т(Ак) и ее звездную развертку Ln для точечной конфигурации An, заданной последовательностью своих точек An — (ab.,ajv) G Ad, с временной сложностью 0(N^+1) + 0(iV^+1)/2J log N).

Основные результаты главы 2 опубликованы в работах [10, 28, 30].

В главе 3 построены некоторые нетривиальные примеры.

В разделе 3.1 построен пример разворачиваемой триангуляции 3-мерного политопа, не имеющей звездной развертки.

В разделе 3.2 построена целочисленная модификация примера М.Е. Rudin [48] неразворачиваемой триангуляции точечной конфигурации, некоторые точки которой имели иррациональные барицентрические координаты. Также показано существование примера триангуляции границы Тд(А') некоторой 4-мерной точечной конфигурации Л', симплициальный комплекс Г(Т°(А')) граней которой не является изоморфным симплициальному комплексу собственных граней ни одного симплициального политопа.

В разделе 3.3 построен пример триангуляции границы 3-мерного куба, для которой не существует порождающей ее триангуляции 3-мерного куба.

В разделе 3.4 построен пример 3-мерной точечной конфигурации В2, где |Z?2| = 14, и множества правильно расположенных тетраэдров с вершинами из В2, которое не может быть дополнено до триангуляции точечной конфигурации В2.

В разделе 3.5 построен пример 4-мерной точечной конфигурации В3, где |Я3| = 15, и множества правильно расположенных и имеющих общую вершину из Г0([Дз]) 4-мерных симплексов с вершинами из В3, которое не может быть дополнено до триангуляции границы точечной конфигурации В3.

Основные результаты главы 3 опубликованы в работах [10, 25, 30].

В главе 4 для некоторых политопов решаются задачи нахождения минимальных триангуляций, описания множества /-векторов триангуляций и описания множества /-векторов <9-триангуляций.

В разделе 4.1 приведены основные определения и свойства, используемые в главе 4. Пусть Т(А) и Тд(А) являются соответственно триангуляцией и d-триангулнцией (/-мерной точечной конфигурации А. Вектор ft(a) = (/J™, .,/JW), рде ftw = |Г,-(Г(Л))|, называется /-вектором триангуляции Т{А). Положим F(A) = {fT(A) : Т(А) £ Т(Д)}. Вектор ft°(a) = (jfW. где /Г(Л) = |Гг(Т9(Л))|, называется /- вектором

0-трпангулпции Тд{А). Положим F9(A) = {f9^ : Тд(А) £ Тд(А)}.

В разделе 4.2 найдены минимальные триангуляции трехмерных политопов из некоторых классов. Минимальное число тетраэдров в триангуляциях политопа М обозначено через и{М). Для трехмерной антипризмы Ап с 2п вершинами и для трехмерной призмы Рп с 2п вершинами устанавливаются

Теорема 4.2.8. v(An) = 3п - 5.

Теорема 4.2.10. и(Рп) = 2п - 4 + [^J.

Доказательства теорем конструктивны и соответствующие минимальные триангуляции строятся КТФМ-алгоритмом.

В разделе 4.3 описывается множество /-векторов триангуляций

4-мерного куба и распределений объема 4-мерного куба по симплексам его триангуляций. При этом все значения этих характеристик реализуются на получаемых вторым ТФМ-алгоритмом триангуляциях 4-мерного куба.

Выпуклую оболочку [Bd] множества точек Bd — {0,l}d будем называть (/-мерным кубом. Через Vol(5) обозначим объем 4-мерного симплекса S С Если Г0(5) С В\ то 4!Vol(S) £ {1,2,3}. Для триангуляции Т(В4) £ Т(В4) положим Ц(Т(В4)) = {S £ Т(В4) : Vol(S) = £}, vJ(Bi) = \ЩТ(В4))\ и vn#) = (^(в4),^),^4)). Положим V(B4) = {>(я4) : Г(В<) £ Т(Я4)} и FV(B4) = : Т(В4) £ Г (В4)}. Тогда имеют место

Теорема 4.3.24. FV(B4) = {(f,v) : / = (16,56,82,55,14) + е4(0,1,4,5,2)+ е3(0,1,3,3,1), г = (4,10,0) + (2е4 + е3)(2,—1,0) + v3(l,-2,1), (с4, v3, с3) £ {1} * {0} * {0,., 8} 1Д0} * {0} * {6,7,8} (J{0} * {1} * {4,., 8}}.

Следствие 4.3.25. F{B4) = {(16,56,82,55,14) + е4(0,1,4,5,2) + е3(0,1,3,3,1) : (с4,е3) £ {1} * {0,. ,8} U {0} * {4,., 8}}.

Следствие 4.3.26. V{B4) = {(24,0,0) + и3(-3,0,1) + г2(—2,1,0) : (из,иг) £ {0} * {0,. ,8}U{1} * {0,. ,4}}.

В разделе 4.4 описывается множество /-векторов триангуляций границы

4-мерного куба.

Из теоремы 4.4.6 следует, что F9(B4) = {(16,56,80,40) + е3(0,1,2,1) : сз £ {0,., 8} }.

В разделе 4.5 описывается множество /-векторов триангуляций границы

5-мерного куба. При этом все /-векторы реализуются на получаемых вторым ТФМ-алгоритмом триангуляциях границы 5-мерного куба.

Теорема 4.5.5. Fd{B5) = {(32,145,280,275,110) +о2(0,1,4,5,2) : а2 £ {25,.,65} }.

Основные результаты главы 4 опубликованы в работах [4, 5, 6, 7, 23, 24].

Список литературы диссертационного исследования кандидат физико-математических наук Груздев, Дмитрий Валентинович, 2006 год

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир. 1979.

2. Бренстед А. Введение в теорию выпуклых многогранников. М.: Мир. 1988.

3. Гельфанд И.М., Зелевинский А.В., Капранов М.М. Дискриминанты много-членовот многих переменных и триангуляции многогранников Ньютона // Алгебра и анализ. 1990. Т.2, Вып. 3. С.1-63.

4. Груздев Д.В. Описание множества /-векторов триангуляций 4-мерного куба. // Материалы четвертой молодежной научной школы по дискретной математике и ее приложениям. Москва: Изд-во мех.-мат. ф-та МГУ. 2000. С.28-32.

5. Груздев Д.В. Модификации алгоритма Фурье-Моцкина для построения триангуляций, их разверток и звездных разверток для точечных конфигураций / Нижегор. гос. ун-т. Н. Новгород, 2006. - 54 с. - Деп. в ВИНИТИ 07.02.06 N 131-В2006.

6. Делоне В.Н. О пустом шаре // Известия АН СССР. 1934. VII серия, 6. С.793-800.

7. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М: Наука. 1981.

8. Зыков А.А. Основы теории графов. М: Наука. 1987. С.118.

9. Математический энциклопедический словарь. М: Сов. энциклопедия. 1988.

10. Моцкин Т.С., Райфа X., Томпсон Дж.Л., Тролл P.M. Метод двойного описания. // Матричные игры. Физматгиз. Москва. 19G1

11. Понтрягин Л.С. Основы комбинаторной топологии. ОГИЗ, 1947.

12. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. М.: Мир. 1989.

13. Черников С.Н. Линейные неравенства. М.: Наука, 1968.

14. Шевченко В.II. Качественные вопросы целочисленного программирования. М.: Физматлит. 1995.

15. Шевченко В.И. О разбиении выпуклого политопа на симплексы без новых вершин. Известия ВУЗ. Математика. N12. 1997. С.89-99.

16. Шевченко В.Н. О максимальных триангулнциях выпуклых политопов. // Международная конференция "Дискретный анализ и исследование операций": Материалы конференции. Новосибирск: Изд-во Ин-та математики. 2000.

17. Шевченко В.II., Груздев Д.В. Модификация алгоритма Фурье-Моцкина для построения триангуляции и ее звездной развертки для точечной конфигурации в общем положении / Нижегор. гос. ун-т. II. Новгород, 2006. - 22 с. - Деп. в ВИНИТИ 07.02.06 N 132-В2006.

18. Шевченко В.II., Чирков АЛО. О покрытии конечно порожденного конуса элементарными конусами. // Инф. бюллетень N4 ассоциации мат. программирования. Екатеринбург, 1993.

19. Энциклопедия элементарной математики. Кн.5. Геометрия. М.: Наука. 1966.

20. Below A., De Loera J.A., Richter-Gebert J. Finding minimal triangulations of convex 3-polytopes is NP-hard. In proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms. January 9-11, 2000.

21. Bohm J. Complete enumeration of all optimal vertex preserving triangulationsof the 5-cube. Forschungsergebnisse, Fredrich-Shiller Universitat, Jena. N/88/36. 1988. P.l-16.

22. Bruggesser H., Mani P. Shellable decompositions of cells and spheres // Math. Scand. V.29. 1971. P.197-205.

23. Burger E. Uber homogene lineare Ungleichungssysteme // Zeitschrift Angewandte Math, und Mech., 1956. V.36. P.135-139.

24. Cottle R.W. Minimal triangulations of the 4-cube // Discrete Math. 1982. V.40. P.25-29.

25. Gruber P.M., Ryskov S.S. Facet-to-facet implies face-to-face // European J. Combin. 1989. V.10. P.83-84.

26. Grunbaurn B. Convex polytopes. N.Y.: Wiley, 1967.

27. Hughes R.B. Lower bounds on cube simplexity // Discrete Math. 1994. V.133. P. 123-138.

28. Hughes R.B. Minimum-cardinality triangulations of the d-cube for d=5 and d=6 // Discrete Math. 1993. V.118. P.75-118.

29. Hughes R.B., Anderson M.R. A triangulation of the 6-cube with 308 simlices // Discrete Math. 1993. V.133. P.253-256.

30. Klee V. A combinatorial analogue of Poincare's duality theorem // Canad. J. Math. 1964. V. 16. P.517-531.

31. Lee C.W. Regular triangulations of convex polytopes, in Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1991. V.4. P.443-456.

32. De Loera J.A. Nonregular Triangulations of Products Of Simplices // Discrete Comput. Geom. 1996. V.15. P.253-264.

33. Mara P.S. Triangulations of the cube // J. Coinbin. Theory Ser. A. 1976. V.20. P. 170-177.

34. Rudin M.E. An unshellable triangulation of a tetrahedron // Bulletin of the American Mathematical Society. 1958. V.64. P.90-91.

35. Sallee J.F. A triangulation of the n-cube // Discrete Math. 1982. V.40. P.81-86.

36. Sallee J.F. A note on minimal triangulations of an n-cube // Discrete Appl. Math. 1982. V.4. P.211-215.

37. Scarf II. The approximation of fixed points of a continuous mapping. // SIAM J. Appl. Math. 1967. V.15, N 5.

38. Stanley R.P. Combinatorics and Commutative Algebra. Series: Progress in mathematics. V.41. Birkhaiiser Boston, 1996.

39. Todd M.J., Tuncel L. A new triangulation for sirnplicial algorithms // SIAM J. Discrete Math. 1993. V.6. P.167-180.

40. Ziegler G.I. Lectures on convex poly topes. Springer-Verlag. 1994.