WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 | 2 ||

Теорема 3.1.5. Для каждого выпуклого d-мерного многогранника P найдется по крайней мере d граней размерности d - 2, задающих пустые соседствующие сферы, и по крайней мере d граней размерности d - 2, задающих полные соседствующие сферы.

Раздел 2.2 посвящен доказательству двумерного дискретного случая.

В разделе 2.3 мы переходим к многомерному случаю и в первую очередь показываем, как можно построить триангуляцию Делоне с помощью поднятия вершин множества на параболоид. Идея этой конструкции принадлежит Вороному.

Четвертый раздел главы посвящен тем идеям, которые использовал Шаттеман в своей попытке доказательства, однако для удобства мы будем использовать наши обозначения и определения.

Определение. Рассмотрим выпуклый симплициальный многогранник общего положения P и триангуляцию Делоне множества его вершин DT (P ) (верхнюю триангуляцию Делоне UDT (P )). Мы будем называть симплекс S DT (P ) (S UDT (P )) D-ухом (UD-ухом), если по крайней мере две фасеты S лежат на границе многогранника P.

В своей работе Шаттеман использует принцип расшелушиваемости (shellability). Давайте дадим формальное определение полиэдрального комплекса и его расшелушивания (shelling).

Определение. Полиэдральный комплексом C в Rd это такой набор многогранников в Rd, что 1) пустое множество принадлежит C, 2) для любого многогранника T C любая его грань T также принадлежит C, 3) пересечение любых двух многогранников из C является гранью каждого из них.

Многогранники из набора, составляющего полиэдральный комплекс, также называются гранями комплекса. Размерностью комплекса C называют наибольшую размерность среди размерностей всех многогранников из C. Максимальные по включению грани комплекса называются фасетами комплекса. Если все фасеты комплекса имеют одну и ту же размерность, комплекс C называется чистым.

Теперь индуктивно определим понятие расшелушиваемости.

Определение. Каждый 0-мерный комплекс является расшелушиваемым, его расшелушивание это любой порядок его 0-мерных фасет.

Пусть теперь C это чистый d-мерный полиэдральный комплекс.

Будем называть C расшелушиваемым, если существует такой порядок (расшелушивание) его фасет (F1, F2,..., Fm), что s : 2 s s-m; ( Ft) Fs – это начало расшелушивания Fs.

t=s Если комплекс C – это d-клетка, то его расшелушивание ( Fs) гоt=меоморфно d-мерному диску для всех s (если это d-сфера, то последний гомеоморфен сфере).

Будем говорить, что фасета F многогранника P видима из точки A, если A и P находятся в разных полупространствах относительно гиперплоскости, проходящей через F. В классической работе Браггессера и Мани44 было доказано, что комплекс граней некоторого выпуклого многогранника, видимых из данной точки, является расшелушиваемым, а также дан метод построения расшелушивания. Просто соединяем данную точку с любой точкой внутри многогранника, и порядок, в котором получившаяся прямая пересекает гиперплоскости, проходящие через видимые фасеты (начиная изнутри многогранника), дает порядок многогранников в расшелушивании. Очевидно, что метод Браггессера и Мани можно применить для симплициального комплекса Делоне. Тем самым верна слудующая лемма.

Лемма 3.4.1. Симплицильный комплекс триангуляции Делоне (верхней триангуляции Делоне) расшелушиваем.

В своей статье Шаттеман доказал также следующую лемму (в работе мы приводим наше доказательство этого утверждения):

Лемма 3.4.2. Последний по порядку симплекс в расшелушивании комплекса Делоне (комплекса верхнего Делоне) является D-ухом (UD-ухом).

Определение. Последний симплекс любого расшелушивания комплекса DT (P ) (UDT (P )), полученный посредством метода Браггессера и Мани для P, называется BMD-ухом (BMUD-ухом).

В разделе 3.5 мы указываем на пробелы в доказательстве Шаттемана, а также приводим контрпример к одному из ключевых утверждений его доказательства.

H. Bruggesser and P. Mani, Shellable decompositions of cells and spheres, Math. Scand., 29 (1971), 197–205.

В разделе 3.6 с помощью леммы 3.4.2 мы доказываем две теоремы, которые являются обобщениями теоремы о четырех вершинах на многомерный случай.

Теорема 3.6.1. Для каждого выпуклого симплициального d-мерного многогранника общего положения P найдутся по крайней мере два BMDуха и по крайней мере два BMUD-уха.

Теорема 3.6.2. Для каждого выпуклого симплициального d-мерного многогранника общего положения P найдутся по крайней мере d + BM-ушей (то есть суммарное число BMD-ушей и BMUD-ушей по крайней мере d + 1).

Стоит заметить, что доказанные нами факты не так сильны, как гипотеза Шаттемана, и, следовательно, она остается открытой.

Четвертая глава посвящена триангуляциям и симплициальным разбиениям выпуклых многогранников.

В разделе 4.1 мы вводим определения и показываем, почему интересующая нас задача нетривиальна.

В разделе 4.2 сделан обзор известных результатов, связанных с симплициальными разбиениями кубов.

В разделе 4.3 мы доказывает теорему об объемных инвариантах симплициальных разбиений призмоидов.

Пусть все вершины n-мерного многогранника P Rn лежат в двух параллельных гиперплоскостях, т.е. P является n-мерным призмоидом.

Для определенности будем считать, что эти гиперплоскости задаются уравнениями x1 = 0 и x1 = s. Будем считать s = 1, так как это никак не влияет на все дальнейшие рассуждения. Пусть у нас также есть разбиение многогранника P на n-мерные симплексы. Обозначим i = {T | ровно i вершин симплекса T лежат в x1 = 0}. Обозначим через qi количество симплексов, лежащих в i, через Tij – j-й симплекс множества i, а через V (Tij) – его n-мерный объем. Пусть для данного призмоида и его разбиения на симплексы V (i) обозначает суммарный объем симплексов из i.

Теорема 4.3.1. V (i) - функция, не зависящая от разбиения, 1 i n.

Доказательство теоремы состоит из последовательного доказательства нескольких лемм.

Рассмотрим Tij и его пересечение Mt с гиперплоскостью x1 = t, где t [0, 1].

Лемма 4.3.2. (n - 1)-мерный объем S(Mt) = cj(1 - t)i-1tn-i, где cj i i некоторая константа, не зависящая от t.

Лемма 4.3.3. Для любого m N многочлены Pi = ti(1 - t)m-i, 0 i m (базисные многочлены Бернштейна), линейно независимы.

Теперь рассмотрим какое-то разбиение многогранника P на симплексы. Определим для него ci() = cj().

i Лемма 4.3.4. ci не зависят от разбиения и определяются только самим многогранником P.

Из последней леммы теорема получается с помощью простого вычисления.

Используя те же методы, что и в доказательстве теоремы 4.3.1, мы доказываем следующий факт.

Следствие 4.3.5. Если выполняются условия теоремы и S(t) const, то V (i) = V (P ). Здесь S(t) (n - 1)-мерный объем сечения P гиперn плоскостью x1 = t.

В разделе 4.4 с помощью следствия 4.3.5 мы показываем, как можно строить нерасширяемое множество симплексов, то есть такое не являющееся разбиением множество неперекрывающихся симплексов с вершинами в вершинах данного многогранника, что к нему нельзя добавить симплекс с вершинами в вершинах данного многогранника, не перекрывающийся с остальными.

В разделе 4.5 изучаются симплициальные разбиения симплициальной призмы, и с помощью следствия 4.3.5 доказывается следующая теорема.

Теорема 4.5.1. Любое разбиение на симплексы симплициальной призмы размерности n содержит ровно n симплексов.

Шестой раздел главы целиком посвящен нижним оценкам на число симплексов в симплициальных разбиениях n-мерных кубов.

В первом подразделе этого раздела с помощью следствия 4.3.5 теоремы 4.3.1 мы строим общую конструкцию для нахождения нижних оценок – некоторый взвешенный объем симплекса, зависящий от матрицы параметров. В общем случае наилучшая оценка получается для матрицы, являющейся решением некоторой задачи линейного программирования, которая слишком сложна для решения уже в размерностях, начиная с семи, поскольку имеет очень много линейных ограничений.

Во втором подразделе раздела 4.6 с помощью общей конструкции из предыдущего подраздела и специального выбора матрицы параметров, воспользовавшись неравенством Адамара, мы получаем новую нижнюю оценку, которая тем не менее все еще хуже, чем найденная Смитомоценка.

В третьем подразделе мы доказываем неравенство на детерминанты 0/1-матриц, с помощью которого при том же выборе матрицы параметров мы получаем оценку, которая экспоненциально улучшает результат Смита.

В последнем подразделе мы используем новую матрицу параметров и с помощью все того же неравенства на детерминанты получаем наилучшую асимптотическую оценку:

Теорема 4.6.6. Для всех натуральных n n-dis(n) (n + 1) =: F3(n) Эта оценка дает очевидное асимптотическое улучшение по сравнению с евклидовой оценкой n n n F3(n) n e lim = lim = = 1.359140914 > A = 1.261522510, n n n E(n) n (2)n e где A – это константа экспоненциального улучшения, полученного Смитом.

Благодарности Автор выражает глубокую благодарность своему научному руководителю профессору Николаю Петровичу Долбилину за постановку задач, их обсуждение и многолетнюю поддержку. Автор также благодарен Алексею Тарасову, Арсению Акопяну, Олегу Мусину, Дирку Фреттлоху и Алексею Гарберу.

Публикации автора по теме диссертации 1. А. А. Глазырин, А. С. Тарасов. Анти-Дюрер гипотеза для невыпуклых многогранников. Успехи математических наук, 64(2009), номер 3, 179-2. А.А. Глазырин, О новом свойстве полиэдральных разбиений, Материалы IX Международного семинара “Дискретная математика и ее приложения”, посвященного 75-летию со дня рождения академика О. Б. Лупанова, 2007, стр. 377-379.

3. D. Frettloh, A. Glazyrin. The lonely vertex problem. Beitrage zur Algebra und Geometrie vol.50, No.1 2009, 71-79.

4. А.А. Глазырин. О симплициальных разбиениях многогранников.

Математические заметки, 85(2009), номер 6, 840-848.

5. А.А. Глазырин. Симплициальные разбиения кубов. Деп. в ВИНИТИ РАН 30.10.2009, №679-В2009, 15 с.

6. А.А. Глазырин. Многомерная теорема о четырех вершинах. Деп. в ВИНИТИ РАН 30.10.2009, №678-В2009, 15 с.

Pages:     | 1 | 2 ||






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»