Решение многогранников: теоретические и вычислительные аспекты тема диссертации и автореферата по ВАК РФ 01.01.04, кандидат физико-математических наук Михалев, Сергей Николаевич

• Михалев, Сергей Николаевич
• кандидат физико-математических наук
• 2003

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

Введение.

1. Метрические октаэдры Брикара 1-го и 2-го типа и их реализуемость в Л3.

1.1. Постановка задачи

1.2. Реализуемость положительных корней многочленов для объёма октаэдров Брикара 1-го и 2-го типа

1.3. К вопросу о выпуклости изометрической реализации с максимальным объемом.

2. Компьютерные методы решения многогранников.

2.1. Программа для решения задачи изометрической реализации по алгоритму Сабитова).

2.2. Некоторые необходимые метрические условия изгибаемости подвесок

3. Об одном методе решения задачи изометрической реализации развёрток.

3.1. Задача изометрической реализации развёртки и методы ее решения.

3.2. Понятие 5-комплекса и некоторые свойства 5-комплексов

3.3. Системы уравнений для решения задачи изометрической реализации

3.4. Об алгоритмическом решении задачи изометрической реализации

3.5. Примеры применения предложенного метода решения задачи изометрической реализации.

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

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

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

2) Изометрические реализации заданных многообразий с метриками в евклидовых или других римановых пространствах.

3) Изгибания данных поверхностей и многогранников.

4) Различные свойства данных поверхностей и многогранников в целом. (Этот круг вопросов составляет предмет внешней геометрии поверхностей.)

В известном смысле второй и третий вопросы являются связующим звеном между первым pi четвертым вопросами; в дифференциальных уравнениях и других областях математики второму и третьему вопросам соответствуют вопросы существования и единственности искомых объектов.

По каждому из перечисленных направлений имеются многочисленные результаты, нашедшие отражение в обширной литературе. Среди геометров, внесших наиболее значительный вклад в геометрию в целом, можно назвать таких классиков как А.Лежандр, О.Коши, Д.Гильберт, Г.Либман, В.Бляшке, С.Э.Кон-Фоссен, Г.Минковский, А.Д.Александров, Н.В.Ефимов, А.В.Погорелов, Ю.Г.Решетняк и др.

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

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

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

С момента построения Брикаром в 1897 году его изгибаемых (имеющих самопересечения) октаэдров ( [17]; см. также [20] и — на русском языке — [11]) на протяжении 80 лет не было известно ни одного примера вложенного изгибаемого многогранника. В 1978 г. такой пример был построен Коннелли (см. [18]).

Вскоре было замечено, что изгибаемый многогранник Коннелли, а также все построенные после него изгибаемые многогранники обладают следующим замечательным свойством: их объём в ходе изгибания остаётся неизменным. Это дало Коннелли основание в своём докладе на Математическом Конгрессе в Хельсинки в 1978 г. высказать так называемую гипотезу кузнечных мехов ("Bellows Conjecture"), состоящую в том, что свойство неизменности объёма является общим для всех изгибаемых многогранников; образно это можно сформулировать как невозможность изготовить идеально точные кузнечные меха из изгибаемых многогранников.

Проблема кузнечных мехов оставалась нерешённой в течение почти 20 лет. Более того, не сущестовало не только доказательства справедливости гипотезы, но не было даже уверенности в том, что гипотеза справедлива. Многие математики, по-видимому, искали ее опровержение, но все попытки найти контрпримеры только подтверждали гипотезу (см., например, [2]).

Справедливость гипотезы кузнечных мехов была доказана И.Х.Сабитовым (см. [13, 14, 22]1). В этих работах доказывается даже более общая теорема, из которой справедливость гипотезы вытекает как простое ее следствие: для всякого многогранника (изгибаемого, или нет) устанавливается существование некоторого нетривиального полиномиального уравнения, такого, что его коэффициенты зависят только от комбинаторного строения и метрики данного многогранника, а объём этого многогранника является его корнем. Так как в ходе изгибания комбинаторное строение и метрика изгибаемого многогранника не меняются, то и объём, будучи этих работах даются разные доказательства основной теоремы; в дальшейшем мы будем ссылаться только на работу [13], поскольку именно в [13] впервые появилось полное доказательство теоремы о многочлене для объёма многогранника (см. далее). корнем полиномиального уравнения с постоянными коэффициентами, не может меняться в ходе изгибания.

Это полиномиальное уравнение позволяет находить объём многогранника по его метрике, точнее, оно дает конечный набор чисел, одно из которых является значением объема многогранника. Рассматриваются только многогранники с треугольными гранями (что не является серьезным ограничением, поскольку нетреугольные грани можно дополнительно триангулировать), следовательно, можно считать, что метрика многогранника с данным комбинаторным строением полностью определяется длинами его рёбер. Таким образом, уравнение для объёма позволяет находить объём многогранника с данным комбинаторным строением, исходя только из длин его рёбер, подобно тому как известная формула Герона позволяет находить площадь треугольника по длинам его сторон.

Продолжая аналогию с планиметрией, ту часть метрической теории многогранников, в которой решаются задачи, связанные с нахождением одного набора метрических характеристик многогранника на основании знания некоторого другого, достаточно богатого, набора метрических характеристик, — своего рода развитие "решения треугольников" — мы будем называть "решением многогранников"2. Теорема об объёме многогранника играет в решении многогранников самую существенную роль.

Поскольку многогранники (в отличие от треугольников) могут быть комбинаторно устроены сколь угодно сложно, неудивительно, что до недавнего времени сколь-нибудь полной теории решения многогранников не существовало вовсе. Однако попытки получить результаты в этом направлении предпринимались довольно давно. Так, например, ещё Jle-жандр в [21] поставил следующий вопрос: какими своими параметрами О многогранник с данным комбинаторным строением определяется однозначно? Сам же Лежандр показал (см. [21]), что число таких параметров равно числу рёбер многогранника, но предположение, что в качестве этих параметров можно взять просто сами рёбра, неверно. (Последнее очевидно в силу существования изгибаемых многогранников: в ходе изгибания все рёбра остаются постоянными, а форма многогранника меняется.) Интересной задачей является нахождение некоторого универсального способа выбора параметров Лежандра.

2термин предложен И.Х.Сабитовым

3Лежандр неявно предполагал многогранник выпуклым, но не обязательно с треугольными гранями

В [13] даётся конструктивное доказательство теоремы об объёме многогранника: предлагается алгоритм, который позволяет исходя из комбинаторного строения и метрики многогранника Р найти все коэффициенты уравнения Q(V) = 0 для объёма. Никакой другой информации о Р не требуется (в частности, не нужно знать длины диагоналей), поэтому найденное уравнение "обслуживает" сразу все изометричные Р многогранники с таким же как у Р комбинаторным строением, в том смысле, что объёмы всех таких многогранников являются корнями одного и того же уравнения Q(V) = 0. Можно сказать, что уравнение Q(V) = 0 со-ставялется лишь по развёртке многогранника. Более того, уравнение для объёма можно составить по методу из [13] ещё до того, как развёртка реализована в виде многогранника, и независимо о того, возможна ли такая реализация в принципе.

Теорема об объёме многогранника, будучи сама по себе фундаментальным результатом, имеет многочисленные применения. Так, в работе [15] для одной из основных задач метрической теории многогранников — задачи изометрической реализации данной развёртки — предлагается решение, основанное на составлении уравнения для объёма.

В работах [13], [14], [15], [22] и в нашей диссертации под развёрткой понимается набор евклидовых треугольников с заданным законом отождествления ("склейки") сторон и вершин, который после отождествления окажется гомеоморфным некоторому компактному ориентируемому многообразию без края, а под изометрической реализацией данной развёртки понимается такой многогранник в для которого данная развёртка является натуральной развёрткой, то есть треугольники развёртки изо-метричны истинным граням многогранника. Таким образом, развёртка и многогранник, являющийся её изометрической реализацией, должны иметь одинаковое комбинаторное строение, а соответствующие треугольники развёртки и грани многогранника должны быть конгруэнтны.

Решать задачу изометрической реализации данной развёртки (или задачу изометрической реализации данной многогранной метрики) в такой постановке до недавнего времени никто не пытался. Так, классическая теорема Александрова [1], которая для всякой заданной на сфере многогранной метрики I положительной кривизны устанавливает существование выпуклого многогранника с внутренней метрикой I, не даёт никакой информации о комбинаторном строении этого многогранника.

Более того, если метрика I была задана как внутренняя метрика некоторой развёртки, гомеоморфной сфере, то, вообще говоря, комбинаторное строение найдённого многогранника, будет отличаться от комбинаторного строения исходной развёртки.

Сказанное относится также к работам Бураго и Залгаллера [6, 7], в которых они доказывают, что всякая развёртка (неважно, есть ли у неё край, и является ли она ориентируемой) допускает изометрическое кусочно-линейное погружение в Л3. В ходе конструктивного доказательства этой теоремы, треугольники исходной развёртки много раз "ломаются" по новым рёбрам, и получаемый многогранник в R3 имеет по сравнению с исходной развёрткой иное (как правило, существенно более сложное) комбинаторное строение.

Таким образом, работа [15] является, по-видимому, первой попыткой решения задачи изометрической реализации развёртки, когда реализация ищется среди многогранников, для которых данная развёртка является натуральной развёрткой. Недостатком метода работы [15] является тот факт, что с его помощью невозможно находить изгибаемые реализации данной развёртки (конечно, речь идет о случае, когда развёртка допускает такие реализации).

Особенностью современной метрической теории многогранников является её ярко выраженная алгоритмическая направленность. С одной стороны, это выражается в широком применении конструктивных доказательств: для того, чтобы доказать сущестовование того или иного объекта, мы просто в явном виде составляем алгоритм построения этого объекта. Таковы, например, доказательства основных теорем в [3], [4], [6], [7], [13], [15]. С другой стороны, в тех случаях, когда нужно проверить, обладает ли данный объект определённым свойством (например, изгибаем ли данный многогранник, реализуема ли в Я3 данная развёртка), мы зачастую не можем заранее дать теоретически полученный ответ, однако можем составить некоторый алгоритм, следуя которому этот ответ в каждом конкретном случае можно получить за конечное число шагов. Такого рода алгоритмический подход используется, например, в [10], [12], [15].

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

Однако, помимо того очевидного соображения, что мы можем использовать компьютер как мощный "вычислитель", т.е. прибор, необходимый для реализации алгоритмов и получения таких конечных результатов, которые интересны сами по себе, существует и другая идея применения компьютера в решении многогранников. Эта идея не нова: компьютер используется для того, чтобы правильно сформулировать ("угадать") теорему. Сначала с помощью компьютера предполагаемое утверждение проверяется для нескольких частных случаев (не слишком сложных, но таких, что вручную соответствующие вычисления провести не удалось бы), а затем формулируется общее утверждение, которое доказывается уже без применения компьютера, теоретически.

В нашей диссертации будут продемонстрированы оба эти подхода.

Помимо исследования свойств многочлена для объёма многогранника и решения задачи изометрической реализации развертки в виде многогранника мы также уделяем внимание изучению изгибаемости многогранников. (Под нетривиальным изгибанием многогранника в R3 понимается такая его непрерывная деформация, при которой грани перемещаются как абсолютно твердые тела, а двугранный угол хотя бы при одном ребре непрерывно изменяется; многогранник, допускающий нетривиальное изгибание называется изгибаемым.) В этой области метрической геометрии есть следующие результаты:

1) Классическая теорема Коши утверждает, что всякий строго выпуклый многогранник неизгибаем. (Доказательство теоремы Коши можно найти, например, в книге [5]).

2 Глюк в [19] доказал, что изгибаемых многогранников в некотором смысле очень мало: в пространстве всех многогранников они заполняют подпространство меры нуль.

3) Брикар в [17] дал полную классификацию изгибаемых октаэдров.

4) Коннелли в [18] построил пример изгибаемого вложенного многогранника.

Конечно, этот список не является полным. Однако, при попытке его продолжить мы убедимся в том, что законченной теории изгибаемых многогранников не существует. Найти какое бы то ни было универсальное необходимое и достаточное условие изгибаемости многогранника — повидимому, чрезвычайно сложная задача (ввиду большого разнообразия комбинаторных строений многогранников). Поэтому всякое продвижение в этом направлении представляет определённый интерес. В главе 2 нашей диссертации мы находим некоторые необходимые метрические условия изгибаемости многогранников имеющих определённое комбинаторное строение (т.н. подвесок, или бипирамид).

Диссертация состоит из введения, трех глав и списка литературы из 30 наименований. Полный объём диссертации — 110 страниц.

Список литературы диссертационного исследования кандидат физико-математических наук Михалев, Сергей Николаевич, 2003 год

1. Александров А.Д. Выпуклые многогранники. //M.-JL: Гостехиздат, 1950.

2. Александров В.А. //Сиб. мат. ж,— 1995.— 36, №6. — С.1215-1224.

3. Астрелин А.В. Сабитов И.Х. Минимальный по степени многочлен для определения объёма октаэдра по его метрике. //Усп. мат. наук. 1995. Т. 50, №5. С. 245-246.

4. Астрелин А.В., Сабитов И.Х. Канонический многочлен для объёма многогранника. //Усп. мат. наук. 1999. Т. 54, №2. С. 165-166.

5. Берже М. Геометрия. //Т. 1. М.: Мир, 1984.

6. Бураго Ю.Д., Залгаллер В.А. Реализация развёрток в виде многогранников. //Вестн. Ленингр. ун-та.— 1960.— Л-7. С.66-90.

7. Бураго Ю.Д., Залгаллер В.А. Изометрические кусочно-линейные погружения двумерных многообразии с полиэдральной метрикой в R3 //Алгебра и анализ. 1995. Т.7, №3. С. 76-95.

8. Кокс Д., Литтл Дж., О'Ши Д. Идеалы, многообразия и алгоритмы. //М. Мир, 2000.

9. Латышев В.И. Комбинаторная теория колец. Стандартные базисы. //Изд. МГУ, 1988, Москва.

10. Сабитов И.Х. Алгоритмическая проверка изгибаемости подвесок. //Укр. геом. сборник, 1987, Т. 30, С. 109-112.

11. Сабитов И.Х. Локальная теория изгибаний поверхностей. //Итоги науки и техники. Совр. пробл. матем. Фундам. напр.— ВИНИТИ.— 1989,— 48.— С.196-270.

12. Сабитов И.Х. Алгоритмы проверки изгибаемости многогранников. //Тр. междунар. конф. "Комплексный анализ. Дифференциальные уравнения. Численные методы и приложения", Т. 6, Уфа, 1996, с. 156166.14