Содержание к диссертации
Введение
ГЛАВА I. Использование многогранных поверхностей в прикладных задачах . 11
1. Аппроксимация областей достижимости многогранниками 11
2. Представление информационных множеств невыпуклыми многогранниками 15
3. Сжимающие отображения 17
4. Проблема Штейнера 19
5. Решение набора задач линейного программирования 20
6. Хранение информации 21
7. Кристаллы 22
ГЛАВА II. Развертки многогранников 23
1. Определения 23
2. Многогранники, не допускающие натуральных разверток 28
3. Доказательство всюду плотности многогранников, имеющих HP 32
ГЛАВА III. Задача о смятом рубле 43
1. Введение 43
2. Постановка задачи, определения и основные результаты 44
3. Описание сетки складывания 47
4. Реализация складывания цветка 51
5. Завершение доказательства. Реализация складывания большого квадрата. 55
6. Наиболее простое складывание, увеличивающее периметр. 58
ГЛАВА IV. Сложность выпуклых стереоэдров . 61
1. Формулировка. 61
2. Доказательство . 63
Заключение, 67
Литература. 68
- Аппроксимация областей достижимости многогранниками
- Многогранники, не допускающие натуральных разверток
- Постановка задачи, определения и основные результаты
- Доказательство
Введение к работе
Актуальность темы.
Диссертация посвящена развитию теории многогранных поверхностей для задач оптимизации.
Важнейшим объектом в задачах оптимизации является множество допустимых решений. Задачи представления и аппроксимации этого множества выпуклыми многогранниками хорошо изучены. Однако во многих прикладных задачах выпуклая аппроксимация поверхностей, ограничивающих множество допустимых решений, является грубой и уводит от существа задачи. Изучение многогранных поверхностей является сложной, малоисследованной математической задачей. Применение теории многогранных поверхностей в таких задачах как, например, задача Штейнера на криволинейной поверхности или задача Лотова о решении системы задач линейного программирования, приводит к качественно новым результатам. Более того, развитие аппарата многогранных поверхностей позволяет формировать математические модели и ставить оптимизационные задачи для многих новых и важных областей науки и техники.
Помимо положения в пространстве, многогранные поверхности имеют свойства внутренней геометрии: площадь; расстояние между точками, как длина кратчайшей кривой, соединяющей точки и лежащей на поверхности; углы между кратчайшими. По-разному расположенные многогранные поверхности в пространстве могут иметь одинаковую внутреннюю геометрию. Это поднимает следующие вопросы: когда две различные поверхности совпадают в смысле внутренней геометрии; можно ли непрерывно перевести одну поверхность в другую при условии выполнения различных ограничений (без самопересечений, без растягиваний, без разрывов и т.п.). Многогранные поверхности могут быть устроены достаточно сложно, даже в окрестности некоторой точки пространства. Они могут касаться сами себя сложным образом. Очевидно, что все это важно при решении прикладных задач, математические модели которых формируется с использованием многогранных поверхностей.
Цель работы и задачи исследования. Целью диссертации является разработка новых типов конструкций многогранных поверхностей, методов работы с ними и применении результатов для решения оптимизационных задач.
Методы исследования. Для решения поставленных задач использовались методы дифференциальной геометрии и комбинаторной геометрии.
В первой главе диссертации приведен обзор задач, где могут применяться методы работы с многогранными поверхностями.
1. Аппроксимация областей достижимости многогранниками. В первом параграфе описывается основная связь задач оптимизации с многогранниками.
Представление информационных множеств исвыпуклыми многогранниками. Во втором параграфе приводится содержательный пример задачи, использующей нсвыпуклые многогранники. Этой задачей является маневрирование космического аппарата с помощью набора микро-двигателей.
Сжимающие отображения. В данном параграфе описывается связь между сжимающим отображением и многослойными поверхностями. Приводятся примеры возможных использований этой связи. Например, метод компьютерного хранения сжимающих отображений.
Задача Штейнера. Известная задача Штейиера имеет следующую формулировку: требуется соединить набор заданных городов сетью дорог, минимизируя общую длину этой сети. Существуют различные варианты этой задачи: общая, прямоугольная, на плоскости, на криволинейной поверхности. Основываясь на идеях развертки можно свести криволинейную задачу к существенно более простому плоскому случаю.
Решение набора задач линейного программирования. В многокритериальном методе достижимых целей возникает ситуация, когда нам нужно решить одновременно большое количество задач линейного программирования (ЛП) на одном и том же многограннике.
Складывание поверхностей. Складывание поверхностей, так же называемое теорией оригами имеет высокий прикладной потенциал. На практике часто встречается ситуация складывания чего-либо трехмерного из плоского листа. Гофрирование листов, складывающиеся антенны, телескопы, упаковка, буклеты и т.д.
Со складыванием поверхностей связан ряд оптимизационных задач: использовать для создания определенной трехмерной конструкции плоский многоугольник минимальной площади, сделать складывание с минимальной суммарной длиной линий сгиба, сложить данный многоугольник в трехмерную фигуру с экстремальными свойствами (максимальный объем, максимальная площадь определенной проекции и т.п.)
Примером может служить задача об упаковке космического телескопа. Необходимо сложить без растяжений, разрывов и склеек определенный плоский многоугольник {плоскую линзу Френеля) в компактную область с цилиндрическим форм фактором, так чтобы суммарная длина линий сгиба была минимальной.
Во второй главе описано решение двух задач, связанных с разверткой, особым типом многогранной поверхности - разрезанной поверхностью многогранника. Важным понятием среди разверток, является натуральная развертка - поверхность многогранника, разрезанная по ребрам, которая, будучи развернута на плоскость, представляет собой самонеперссекающийся многоугольник.
Рис. 1: Натуральная развертка куба
Еще один тип разверток - развертка Вороного, которая образуется следующим образом: возьмем некоторую точку на поверхности многогранника - О. Теперь определим множество разрезов - вес такие точки X, для которых существует две и более одной кратчайших ОХ. Эта область является графом, разрезав по которой мы и получим развертку Вороного.
Доказаны две теоремы, иллюстрирующие свойства разверток:
Теорема II.1. Существует невыпуклая полиэдральная сфера с выпуклыми гранями, не допускающая ни одной натуральной развертки.
Основная идея теоремы изображена на рисунке 3. Многогранник, у которого нет натуральной развертки, получается добавлением треугольных пирамид в каждой из вершин некоторого выпуклого многогранника (например, куба). Эти пирамиды могут быть сколь угодно малыми. Одним из выводов из этой теоремы является то, что для невьшуклых многогранников обычная аппроксимация может не сохранять такое существенное свойство как натуральная развертка.
Теорема II.2. Для любого выпуклого многогранника Р и его развертки Вороного существует ^-близкий ему многогранник Р' в смысле расстояния Хаусдорфа такой, что он имеет натуральную развертку.
Рис. 2; Развертка Вороного для куба с центром в точке О
Принцип доказательства этой теоремы основан на следующем. Построим развертку Вороного на многограннике Р. Теперь подразобьем вес грани многогранника Р, но линиям развертки Вороного. Получился но строго выпуклый многогранник, у которого
Рис. 3: Многогранник с выпуклыми гранями, не имеющий развертки. есть натуральная развертка.
Теперь остается с помощью малых шевелений сделать этот многогранник строго выпуклым. Одной из основных идей при создании строго выпуклого многогранника является "поднятие разбиения Вороного" на параболоид. То есть получается выпуклая многогранная поверхность, описанная вокруг параболоида и реберный остов которой при проекции на плоскость вдоль оси параболоида дает исходную развертку Вороного.
Эта теорема устанавливает связь между понятиями натуральной развертки и развертки Вороного. А так же доказывает, что множество многогранников, имеющих натуральную развертку всюду плотно. Кроме этого теорема предъявляет конструктивный метод построения аппроксимации многогранника, которая будет иметь натуральную развертку.
Данная модель является основой для построения эффективных алгоритмов для решения задачи Штейнера и близкую к ней задачу решения набора задач линейного программирования.
Для случая задачи Штейнера на плоскости аппарат решения развит и существуют относительно эффективные алгоритмы. Здесь помогает тот факт, что кратчайшим графом, соединяющим две точки, является отрезок. В случае задачи Штейнера для криволинейной поверхности все усложняется. Даже между двумя точками уже не так просто найти кратчайшую, связывающую линию. Это можно сделать с помощью разверток.
Основываясь на описанных выше идеях можно свести случай криволинейной поверхности к случаю на плоскости. Например, возможна следующая схема: разворачиваем специальным образом криволинейную поверхность на плоскость. Далее решаем задачу Штейнера на плоскости. Находим все локально оптимальные варианты.
Рис. 4: Цветок
Переводим их обратно на криволинейную поверхность и уточняем получившуюся длину. Выбираем вариант с минимальной суммарной длиной - это и будет решение задачи Штейнера.
В третьей главе приводится конструкция многослойной поверхности, описываются различные свойства и методы работы с нею.
В первом параграфе вводятся основные понятия: Сеткой складывания называется разбиение данного многоугольника Р на несколько непересекающихся многоугольников Pjf так что пересечением любых двух из них является общая сторона или общая вершина.
Складыванием Р' называется отображение односвязного многоугольника Р такое, что каждый многоугольник Pt отображается изометрично, а образы соседних многоугольников, отображаются по одну сторону относительно общей стороны.
Приводятся свойства многогранной поверхности, вытекающие из теоремы Кавасаки:
К каждой внутренней вершине сетки складывания подходит четное количество ребер.
Сумма углов вокруг этой вершины, взятых через один равна 180.
Процессом складывания назовем гомотопию, непрерывно переводящую Р в Р', изометричную на каждом из многоугольников Рг
Процесс складывания называется реализуемым, если для процесса складывания существует сколь угодно близкая изотопия (уже не изометричная).
Во втором параграфе приводится доказательство следующей леммы: Последовательность складываний вдоль прямой имеет реализуемый процесс складывания.
В оригами существует набор различных приемов складывания поверхностей. Несмотря на то, что каждое из этих складываний вполне очевидно складывается с помощью обычной бумаги, далеко не для всех существует строгое обоснование того, что это складывание осуществляется без растяжений. Возникает задача классификации складываний, которые можно проводить без растяжений.
Рис. 5: Складывание треугольника радиальной "гармошко" со сгибом.
Обоснован новый метод складывания радиальной "гармошкой" со сгибом. Этот метод является новым, неизвестным ранее способом складывания и является обобщением "вывернутых складок" (Crimp folds). Берем произвольную фигуру. На границе выбираем вершину О, откуда проводится набор лучей под равными углами. Лучи разбиваются на четные и нечетные. На каждом луче отмечается точка. Расстояние от О до точек на всех четных (нечетных) лучах совпадает. Соединяя последовательно точки линиями, получаем ломаную - цветок (рис. 4). Теперь эту фигуру можно сложить, как показано на рисунке 5.
Доказательство этого факта состоит из двух частей. Сначала доказываем, что можно произвести процесс складывания без сгибания по линиям цветка, но так, что все эти линии находятся в одной плоскости. Далее, в каждый момент времени симметрично отображаем конструкцию относительно плоскости, проходящей через цветок. В результате получаем искомый процесс складывания. Кроме качественного объяснения в диссертации так же приводятся точные координаты каждой точки в процессе складывания, доказывается реализуемость. В конце третьего параграфа, показывается возможность одновременного складывания стопки бумаги с разными цветками. Цветки должны при этом быть гомотетичны и их размеры должны быть тем меньше, чем выше находится слой.
На основе этих методов доказывается следующая теорема:
Теорема III. 1: Для данного квадрата Р существует реализуемое складывание такое, что периметр сложенного многоугольника Р' превосходит любое наперёд заданное число.
Доказательство проходит в два этапа: Сначала предъявляется сетка складывания, доказывается её корректность. Показывается сложенная фигура F и дается оценка снизу для периметра Р' в зависимости от параметров сетки складывания N к К. На втором этапе приводится процесс складывания и доказывается его реализуемость.
Эта теорема может быть положена в основу решения задачи, которую поставил В.И. Арнольд более 50 лет назад. Так же она известна как задача о салфетке Маргулиса в теории оригами. Представим себе прямоугольный лист бесконечно тонкой нерастяжимой бумаги. Согнув по определенным линиям, можно сложить прямоугольник в некоторый другой плоский многоугольник. Можно ли в результате таких сгибаний получить многоугольник большего, чем у исходного прямоугольника, периметра?
Исходя из теоремы III. 1 можно заключить, что ответом на этот вопрос утвердительный.
Процесс складывания алгоритмизуем и разработано соответственное программное обеспечение.
Для следующей оптимизационной задачи, найти складывание, максимизирующее периметр, получен следующий результат: оценки сверху не существует. Результат подтвержден вычислительно, и соответствующие иллюстрации приводятся в работе.
В четвертой главе в предыдущих главах были изучены такие важные свойства многогранных поверхностей, как "разрезаемость", "складываемость", "изгибаемость". В этой главе изучается ещё одно важнейшее свойство этих поверхностей - количество граней. Задачи такого типа имеют ярко выраженную прикладную направленность (например} создание кристаллических структур с новыми свойствами).
В диссертации разработан метод оценки числа граней в и на его основе улучшена оценка Делоне-Сандаковой для количества граней стереоэдра - многогранника заполняющего пространство регулярным образом.
Теорема IV. 1. Число d ~ 1-граней выпуклого нормального d-мерного стереоэдра не превышает: 2d(2dd! - 1/2) — 2 Эта теорема является небольшим улучшением для оценки Делоне-Сандаковой. Например, для d = 3 оценка улучшилась с 390 до 378.
Аппроксимация областей достижимости многогранниками
Еще один тип разверток - развертка Вороного, которая образуется следующим образом: возьмем некоторую точку на поверхности многогранника - О. Теперь определим множество разрезов - вес такие точки X, для которых существует две и более одной кратчайших ОХ. Эта область является графом, разрезав по которой мы и получим развертку Вороного.
Доказаны две теоремы, иллюстрирующие свойства разверток: Существует невыпуклая полиэдральная сфера с выпуклыми гранями, не допускающая ни одной натуральной развертки.
Основная идея теоремы изображена на рисунке 3. Многогранник, у которого нет натуральной развертки, получается добавлением треугольных пирамид в каждой из вершин некоторого выпуклого многогранника (например, куба). Эти пирамиды могут быть сколь угодно малыми. Одним из выводов из этой теоремы является то, что для невьшуклых многогранников обычная аппроксимация может не сохранять такое существенное свойство как натуральная развертка.
Теорема II.2. Для любого выпуклого многогранника Р и его развертки Вороного существует -близкий ему многогранник Р в смысле расстояния Хаусдорфа такой, что он имеет натуральную развертку.
Принцип доказательства этой теоремы основан на следующем. Построим развертку Вороного на многограннике Р. Теперь подразобьем вес грани многогранника Р, но линиям развертки Вороного. Получился но строго выпуклый многогранник, у которого есть натуральная развертка.
Теперь остается с помощью малых шевелений сделать этот многогранник строго выпуклым. Одной из основных идей при создании строго выпуклого многогранника является "поднятие разбиения Вороного" на параболоид. То есть получается выпуклая многогранная поверхность, описанная вокруг параболоида и реберный остов которой при проекции на плоскость вдоль оси параболоида дает исходную развертку Вороного.
Эта теорема устанавливает связь между понятиями натуральной развертки и развертки Вороного. А так же доказывает, что множество многогранников, имеющих натуральную развертку всюду плотно. Кроме этого теорема предъявляет конструктивный метод построения аппроксимации многогранника, которая будет иметь натуральную развертку.
Данная модель является основой для построения эффективных алгоритмов для решения задачи Штейнера и близкую к ней задачу решения набора задач линейного программирования.
Для случая задачи Штейнера на плоскости аппарат решения развит и существуют относительно эффективные алгоритмы. Здесь помогает тот факт, что кратчайшим графом, соединяющим две точки, является отрезок. В случае задачи Штейнера для криволинейной поверхности все усложняется. Даже между двумя точками уже не так просто найти кратчайшую, связывающую линию. Это можно сделать с помощью разверток.
Основываясь на описанных выше идеях можно свести случай криволинейной поверхности к случаю на плоскости. Например, возможна следующая схема: разворачиваем специальным образом криволинейную поверхность на плоскость. Далее решаем задачу Штейнера на плоскости. Находим все локально оптимальные варианты. Переводим их обратно на криволинейную поверхность и уточняем получившуюся длину. Выбираем вариант с минимальной суммарной длиной - это и будет решение задачи Штейнера. В третьей главе приводится конструкция многослойной поверхности, описываются различные свойства и методы работы с нею. В первом параграфе вводятся основные понятия: Сеткой складывания называется разбиение данного многоугольника Р на несколько непересекающихся многоугольников Pjf так что пересечением любых двух из них является общая сторона или общая вершина. Складыванием Р называется отображение односвязного многоугольника Р такое, что каждый многоугольник Pt отображается изометрично, а образы соседних многоугольников, отображаются по одну сторону относительно общей стороны. Приводятся свойства многогранной поверхности, вытекающие из теоремы Кавасаки: 1. К каждой внутренней вершине сетки складывания подходит четное количество ребер. 2. Сумма углов вокруг этой вершины, взятых через один равна 180. Процессом складывания назовем гомотопию, непрерывно переводящую Р в Р , изометричную на каждом из многоугольников Рг Процесс складывания называется реализуемым, если для процесса складывания существует сколь угодно близкая изотопия (уже не изометричная). Во втором параграфе приводится доказательство следующей леммы: Последовательность складываний вдоль прямой имеет реализуемый процесс складывания. В оригами существует набор различных приемов складывания поверхностей. Несмотря на то, что каждое из этих складываний вполне очевидно складывается с помощью обычной бумаги, далеко не для всех существует строгое обоснование того, что это складывание осуществляется без растяжений. Возникает задача классификации складываний, которые можно проводить без растяжений.
Обоснован новый метод складывания радиальной "гармошкой" со сгибом. Этот метод является новым, неизвестным ранее способом складывания и является обобщением "вывернутых складок" (Crimp folds). Берем произвольную фигуру. На границе выбираем вершину О, откуда проводится набор лучей под равными углами. Лучи разбиваются на четные и нечетные. На каждом луче отмечается точка. Расстояние от О до точек на всех четных (нечетных) лучах совпадает. Соединяя последовательно точки линиями, получаем ломаную - цветок (рис. 4). Теперь эту фигуру можно сложить, как показано на рисунке 5.
Доказательство этого факта состоит из двух частей. Сначала доказываем, что можно произвести процесс складывания без сгибания по линиям цветка, но так, что все эти линии находятся в одной плоскости. Далее, в каждый момент времени симметрично отображаем конструкцию относительно плоскости, проходящей через цветок. В результате получаем искомый процесс складывания. Кроме качественного объяснения в диссертации так же приводятся точные координаты каждой точки в процессе складывания, доказывается реализуемость. В конце третьего параграфа, показывается возможность одновременного складывания стопки бумаги с разными цветками. Цветки должны при этом быть гомотетичны и их размеры должны быть тем меньше, чем выше находится слой.
На основе этих методов доказывается следующая теорема: Теорема III. 1: Для данного квадрата Р существует реализуемое складывание такое, что периметр сложенного многоугольника Р превосходит любое наперёд заданное число.
Многогранники, не допускающие натуральных разверток
В этой главе рассматривается и решается известная проблема поставленная Арнольдом в 1956 году ([3],([4]). Краткая формулировка задачи о "мятом рубле" (можно ли увеличить периметр многоугольника последовательностью сгибаний [3]) нуждается в уточнении.
По сути, эта задача является задачей о существовании изометричного преобразования многогранной поверхности в плоскую многоугольную фигуру со сколь угодно большим периметром. Представим себе прямоугольный лист бесконечно тонкой нерастяжимой бумаги. Будем сгибать его каждый раз вдоль прямой, пересекающей этот лист или некоторому отрезку в какой-то плоский многоугольник.
Можно ли в результате таких сгибаний превратить в многоугольник большего, чем у исходного прямоугольника, периметра?
Если при каждом сгибании ограничиваться сгибанием фигуры вдоль целой прямой, то легко получить ответ: периметр при каждом сгибании строго уменьшается (гл. III 2.), Однако, класс изометричных деформаций гораздо шире, чем множество композиций сгибаний вдоль целых прямых, и на этом же классе указанная задача становится содержательной.
Мы рассмотрим сетки складывания прямоугольника и покажем, что среди них существует такая сетка, что вдоль её ребер можно сложить прямоугольник так, что любые два многоугольника сетки, имеющие общее ребро изометрично отображаются в многоугольники, лежащие в одной плоскости и по одну сторону от прямой, несущей образ данного ребра.
Более того, мы покажем, что этот процесс складывания можно реализовать "физически", то есть результирующее отображение прямоугольника и некоторый многоугольник можно связать с тождественным преобразованием прямоугольника на себя такой гомотопией которая отображает каждую клетку сетки складывания в пространство изометрично. При этом образы двух клеток могут частично совпадать, но не "могут проходить сквозь". Другими словами при этой гомотопии соблюдаются естественные правила сгибания бесконечно тонкого, по не растяжимого листа бумаги.
Задача о смятом рубле так же является известной задачей в теории оригами. Оригами это древнее японской искусство складывания различных фигур из квадратного листа бумаги. Оригами вызвало целый ряд математических вопросов, что послужило появлению теории оригами. Первая теорема, которая появилась в оригами является "теорема Кавасаки" [34], которая формулируется так: "Для того чтобы данная сетка складывания могла сложиться в плоское оригами, необходимо, чтобы вокруг каждой вершины альтернированная сумма углов была равна 0". Под плоским оригами подразумевается сложенная по данной сетке складывания плоская фигура. Для того, чтобы осуществить процесс складывания, этого недостаточно. Однако если пренебречь самим процессом складывания и задаться вопросом существования лишь конечного результата, то данного условия оказывается достаточно для существования плоского оригами (гл. III 2.). 2. Постановка задачи, определения и основные результаты. Пусть плоский многоугольник Р разбит на многоугольники Pt Р , смежные по целым сторонам. Такое разбиение будем обозначать через L. Определение III.1. Пусть для данного разбиения L плоского многоугольника Р, существует отображение / :Р - Е1 такое что: (F1) Др - линейная изометрия многоугольника Pt є L\ (F2) если Pt и Р. имеют общую сторону е, то образы /(Pt) и /(Р) лежат по одну сторону от прямой, содержащей /(e); Такое отображение мы назовем складыванием многоугольника Р, образ /" = /(F) -сложенным многоугольником, реберный граф разбиения L - сеткой (складывания). Лемма III. 1. Для односвязіюго многоугольника Р и сетки L существует складывание (вообще говоря нереализуемое, см опр. 2) тогда и только, когда для каждой внутренней вершины этой сетки выполняются следующие условия: (1) к вершине подходит четное количество ребер; (2) альтернированная сумма углов вокруг вершины равна нулю; Отметим, что под альтернированной суммой понимаем сумму, в которую два угла сходящихся в вершине и смежных по стороне, входят с противоположным знаком. Доказ ательство. 1. Необходимость. К вершине V подходит к ребер и к многоугольников из L. Перенумеруем ребра по часовой стрелке - eirek+l = еї. Обозначим многоугольники через P.,et є Pj,eM є Рг Так как соседние многоугольники после складывания должны лежать по одну сторону от общего ребра, к должно быть чётным. Если после складывания угол at между ребрами et и et+l откладывается в положительном направлении от ребра et, то угол аг(.+] между ei+l и е.+2 откладывается в отрицательном направлении. При откладывании угла ак, еА+1 должно совпасть с е,. Поэтому альтернированная сумма этих углов должна быть равна 0. 2. Достаточность. Пусть дана сетка L с условиями (1), (2) и пусть дано изометричное отображение некоторого многоугольника, скажем Р1 из L, f(Px) : Pj -» Р[ є R.2. Возьмем сильно-связную цепочку, соединяющую / ! с Р2 є і. Тогда отображение _ДР,) однозначно продолжается вдоль цепочки до отображения ДР2): Р2 - 2 є R2 при условии выполнения (F1) и (F2). Отображение f{P2) не зависит от выбора цепочки. Действительно, в силу односвязности многоугольника Р любую сильносвязную цепочку, соединяющую Р, с Р2 можно перестроить в другую сильносвязную цепочку, соединяющую Рх с тем же Р2 только с помощью элементарных перестроек в окрестности отдельной вершины. Такая перестройка в силу условий 1 и 2 не меняет отображения f(P2)
Постановка задачи, определения и основные результаты
В этой главе рассматривается и решается известная проблема поставленная Арнольдом в 1956 году ([3],([4]). Краткая формулировка задачи о "мятом рубле" (можно ли увеличить периметр многоугольника последовательностью сгибаний [3]) нуждается в уточнении.
По сути, эта задача является задачей о существовании изометричного преобразования многогранной поверхности в плоскую многоугольную фигуру со сколь угодно большим периметром. Представим себе прямоугольный лист бесконечно тонкой нерастяжимой бумаги. Будем сгибать его каждый раз вдоль прямой, пересекающей этот лист или некоторому отрезку в какой-то плоский многоугольник.
Можно ли в результате таких сгибаний превратить в многоугольник большего, чем у исходного прямоугольника, периметра? Если при каждом сгибании ограничиваться сгибанием фигуры вдоль целой прямой, то легко получить ответ: периметр при каждом сгибании строго уменьшается (гл. III 2.), Однако, класс изометричных деформаций гораздо шире, чем множество композиций сгибаний вдоль целых прямых, и на этом же классе указанная задача становится содержательной. Мы рассмотрим сетки складывания прямоугольника и покажем, что среди них существует такая сетка, что вдоль её ребер можно сложить прямоугольник так, что любые два многоугольника сетки, имеющие общее ребро изометрично отображаются в многоугольники, лежащие в одной плоскости и по одну сторону от прямой, несущей образ данного ребра. Более того, мы покажем, что этот процесс складывания можно реализовать "физически", то есть результирующее отображение прямоугольника и некоторый многоугольник можно связать с тождественным преобразованием прямоугольника на себя такой гомотопией которая отображает каждую клетку сетки складывания в пространство изометрично. При этом образы двух клеток могут частично совпадать, но не "могут проходить сквозь". Другими словами при этой гомотопии соблюдаются естественные правила сгибания бесконечно тонкого, по не растяжимого листа бумаги. Задача о смятом рубле так же является известной задачей в теории оригами. Оригами это древнее японской искусство складывания различных фигур из квадратного листа бумаги. Оригами вызвало целый ряд математических вопросов, что послужило появлению теории оригами. Первая теорема, которая появилась в оригами является "теорема Кавасаки" [34], которая формулируется так: "Для того чтобы данная сетка складывания могла сложиться в плоское оригами, необходимо, чтобы вокруг каждой вершины альтернированная сумма углов была равна 0". Под плоским оригами подразумевается сложенная по данной сетке складывания плоская фигура. Для того, чтобы осуществить процесс складывания, этого недостаточно. Однако если пренебречь самим процессом складывания и задаться вопросом существования лишь конечного результата, то данного условия оказывается достаточно для существования плоского оригами (гл. III 2.). 2. Постановка задачи, определения и основные результаты. Пусть плоский многоугольник Р разбит на многоугольники Pt Р , смежные по целым сторонам. Такое разбиение будем обозначать через L. Определение III.1. Пусть для данного разбиения L плоского многоугольника Р, существует отображение / :Р - Е1 такое что: (F1) Др - линейная изометрия многоугольника Pt є L\ (F2) если Pt и Р. имеют общую сторону е, то образы /(Pt) и /(Р) лежат по одну сторону от прямой, содержащей /(e); Такое отображение мы назовем складыванием многоугольника Р, образ /" = /(F) -сложенным многоугольником, реберный граф разбиения L - сеткой (складывания). Лемма III. 1. Для односвязіюго многоугольника Р и сетки L существует складывание (вообще говоря нереализуемое, см опр. 2) тогда и только, когда для каждой внутренней вершины этой сетки выполняются следующие условия: (1) к вершине подходит четное количество ребер; (2) альтернированная сумма углов вокруг вершины равна нулю; Отметим, что под альтернированной суммой понимаем сумму, в которую два угла сходящихся в вершине и смежных по стороне, входят с противоположным знаком. Доказ ательство. 1. Необходимость. К вершине V подходит к ребер и к многоугольников из L. Перенумеруем ребра по часовой стрелке - eirek+l = еї. Обозначим многоугольники через P.,et є Pj,eM є Рг Так как соседние многоугольники после складывания должны лежать по одну сторону от общего ребра, к должно быть чётным. Если после складывания угол at между ребрами et и et+l откладывается в положительном направлении от ребра et, то угол аг(.+] между ei+l и е.+2 откладывается в отрицательном направлении. При откладывании угла ак, еА+1 должно совпасть с е,. Поэтому альтернированная сумма этих углов должна быть равна 0. 2. Достаточность. Пусть дана сетка L с условиями (1), (2) и пусть дано изометричное отображение некоторого многоугольника, скажем Р1 из L, f(Px) : Pj -» Р[ є R.2. Возьмем сильно-связную цепочку, соединяющую / ! с Р2 є і. Тогда отображение _ДР,) однозначно продолжается вдоль цепочки до отображения ДР2): Р2 - 2 є R2 при условии выполнения (F1) и (F2). Отображение f{P2) не зависит от выбора цепочки. Действительно, в силу односвязности многоугольника Р любую сильносвязную цепочку, соединяющую Р, с Р2 можно перестроить в другую сильносвязную цепочку, соединяющую Рх с тем же Р2 только с помощью элементарных перестроек в окрестности отдельной вершины. Такая перестройка в силу условий 1 и 2 не меняет отображения f(P2) Определение II 1.2. Назовем гомотопию ft процессом складывания для данного разбиения L и складывания f:P- Е2, когда выполнены следующие условия: 1. /0 - тождественное отображение, a /j = /; 2. для любого Р; є L и любого t є [0,1], ограничение ft\P — линейная изометрия; Определение II 1.3. Для данного разбиения L складывание f : Р - Е2 называется реализуемым, если существует процесс складывания ft который сколь угодно близко аппроксимируется изотопией пространства Е3, для t є [0, 1]; Такую гомотопию будем называть реализацией складывания. Условия сколь угодно близкой изотопии описывает процесс реального складывания листа бумаги, при котором части листа бумаги могут касаться друг друга, складываться в одну плоскость, но не могут пересекать друг друга или проходить сквозь. Докажем следующую полезную лемму: Лемма Ш.2. Пусть складывание f есть композиция двух складываний f и f где /"j реализуемое складывание, а /" - складывание вдоль некоторой прямой. Тогда складывание /, так же является реализуемым. Гомотопия ft состоит из двух частей, при t є [О, /J это Д, при t є [t[t t2] это f" f t. Без ограничения общности можно считать что /" это складывание относительно прямой у = 0, полуплоскости у 0 на полуплоскость у 0. Точные координаты гомотопии:
Доказательство
Пусть Т = tv...,td трансляционная подгруппа кристаллографической группы Sym(T), имеющая базис [tlr...,td) . Семейство многогранников изоэдрального разбиения распадается на h смежных классов по подгруппе Т. Заметим, что объем стереоэдра равен Vp — j[ VT, где VT — объем основного параллелепипеда решетки Т. Теорема IV. 1. Число (d-1)- мерных граней выпуклого нормального (/-мерного стереоэдра с h смежными классами не превышает Доказательство оценки построено следующим образом. В соответствии с тем как группа Symi D разбивается на А смежных классов по Т (смежных решеток), совокупность многогранников разбиения Траспадается на А совокупностей 7 (решеток стереоэдров). Пусть Р є 7 . В ([9]) доказано, что число стереоэдров из той же решетки Tt, имеющих с Робщую ((/— 1)-грань, не превышает 2(2 -1). Далее, число стереоэдров из любой другой решетки Tjt j Ф і, имеющих с Р общую (d - 1)-грань, не превышает 2d. Суммируя по классам смежности, получаем оценку (1). В нашей работе оценка (1) будет снижена за счет уменьшения вклада во множество граней со стороны стереоэдров из той же решетки, что и Р, атак же из смежной решетки, получаемой из данной инверсией, при условии h 2dd\ Предложение 1 Объем J-мерпого симплекса вершинами в точках решетки Т кратен -jf. Для доказательства см. ([12). Предложение 2 Объем выпуклой фигуры, содержащей d отрезков, не меньше объема симплекса, у которого все d ребер, выходящие из одной вершины, равны и параллельны данным отрезкам. Доказательство в {[19]). Лемма IV. 1. Если индекс А, к й dl, то в разбиении Тстереоэдр Р є Т{ не может иметь более 2 -2 общих граней со стереоэдрами из той же решетки 7 г Будем говорить, что два стереоэдра F и Р" из одной решетки эквивалентны по mod 2, если F = Р" + t, где / - вектор решетки Т, имеющий лишь четные координаты: t = 0 (mod 2). Тогда стереоэдры данной решетки Tt распадаются на 1d классов эквивалентности по mod 2. В [13] было доказано, что данный стереоэдр Р є Т) в каждом классе эквивалентности решетки Т. не может иметь более 1 соседа по (d — 1)-грани, если Р не принадлежит этому классу, и не может иметь ни одного соседа из того же класса эквивалентности. Доказательство леммы основано на следующем замечании. Пусть многогранник Р имеет общую (d — іугрань F с многогранником Р{ — Р + t, где t є Г с Sym(T). Образ этой грани F - t является также (d — 1)-грапыо стереоэдра Р. Возьмем точки М є F — t и М — М + t є F. Мы видим, что для трансляционного вектора смежности t стереоэдра Р найдется пара точек М, М , такая что MM = t и М, М є Р. Так как Р имеет не более двух общих (d — 1)-граней со стереоэдрами чужого класса эквивалентности и ни одной общей (d - 1)-грани со стереоэдрами своего класса эквивалентности, то стереоэдр Р и смежные по ним стереоэдры принадлежат попарно разным классам эквивалентности. Пусть стереоэдр Р имеет более 2(2 -1 - 1) граней, общих со стереоэдрами из той же решетки, то есть со стереоэдрами вида Р + Т. Так как в любой (d - 1)-мерной подрешетке решетки Т лежит не более 2rf"1 классов эквивалентности {mod 2), то множество всех трансляционных векторов смежности t. не может лежать в одном ( /— 1)-мерном подпространстве и, следовательно, векторы t,- = МЩ, линейно независимы, где МРМ\ є Р. Поэтому объем Vp ViConviU M.Mj])) Ф 0. В силу Предложения 2, объем не менее объема Vs невырожденного симплекса S, натянутого на d линейно независимых векторов tj, j = 1,2,..., d Так как tf - є Т, то V 4 VT, где VT - объем фундаментального параллелепипеда решетки Т. Так как h d\, то что противоречит соотношению Vp = \-VT. Лемма IV.1 доказана. Допустим, что в группе SymifT) имеется движение у, которое есть суперпозиция некоторой инверсии в точке и трансляции (каждое из них в отдельности может не принадлежать группе Sym(7 )). С другой стороны, такая суперпозиция у может быть представлена в виде чистой инверсии (вообще говоря, в другой точке). Доказательство. Пусть точка О - центр тяжести многогранника Р, которая в силу выпуклости Р есть внутренняя точка многогранника Р центром О. Пусть Pf - стереоэдр из 1(Р), смежный с Л по общей ((/ - 1)-грани F{ и пусть yt є Sym(T), такое что у Р) = Рг Инволюция yi переводит грань Ft в себя. Следовательно, единственная неподвижная точка Mt инверсии у; является внутренней точкой грани Fr Заметим,что А/, середина отрезка ОО а вектор Ofi. - примитивный вектор решетки , то есть Oflj /= 0 (mod 2) (для доказательства см. [12],[13]). Предположим, что Р имеет больше 2 -1 граней, общих со стереоэдрами из решетки 1(Р) и следовательно столько же точек Ov Отсюда, так как центры Ot принадлежат попарно различным классам эквивалентности по (mod 2), то множество всех центров 0( не может лежать ни в каком (я — 1 )-мерном подпространстве. Поэтому объем V(Conv(0.)) Ф О и, следовательно,
