авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Дискретные трансверсали выпуклых множеств

На правах рукописи

Акопян Арсений Владимирович ДИСКРЕТНЫЕ ТРАНСВЕРСАЛИ ВЫПУКЛЫХ МНОЖЕСТВ Специальность 01.01.09 Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико–математических наук

Ярославль 2010

Работа выполнена в Учреждении Российской академии наук Институте системного анализа РАН.

Научные руководители: доктор физико-математических наук, профессор Владимир Леонидович Дольников доктор физико-математических наук, профессор Александр Петрович Афанасьев

Официальные оппоненты: доктор физико-математических наук, профессор Николай Петрович Долбилин кандидат физико-математических наук, доцент Роман Николаевич Карасёв

Ведущая организация: Московский государственный университет имени М.В. Ломоносова

Защита состоится 28 декабря 2010г. в 16:00 часов на заседании диссертацион ного совета Д 212.002.03 при Ярославском государственном университете им. П. Г. Демидова, расположенном по адресу: 150008 г. Ярославль, ул.

Союзная, д. 144, аудитория 426.

С диссертацией можно ознакомиться в библиотеке Ярославского государствен ного университета им. П. Г. Демидова.

Автореферат разослан 2010г.

Учёный секретарь диссертационного совета Яблокова С. И.

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

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

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

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

Также доказывается кусочно-линейный аналог теоремы Киршбрауна, о про должении сжимающего отображения. Теорема Киршбрауна тесно связана с теоремой Хелли, то есть с существованием 1-трансверсали у семейства шаров.

В третьей главе доказан кусочно-линейный аналог теоремы Нэша–Кей пера. Этот вариант теоремы можно интерпретировать, как существование конечной трансверсали для семейства шаров в метрических пространствах специального вида.

Напомним формулировку классической теоремы Хелли. Здесь и далее через Ed будем обозначать d-мерное евклидово пространство.

Теорема Хелли. Если P семейство выпуклых компактных множеств в Ed такое, что пересечение любых d + 1 из них не пусто, то пересечение всех множеств из P не пусто.

Естественным является следующий вопрос: каким требованиям долж но удовлетворять семейство множеств, чтобы его можно было разбить на k частей, каждая из которых имеет непустое пересечение. В этом случае, множество из k точек протыкающих (piercing) все множества семейства называют k-трансверсалью.

Вопросы о существовании k-трансверсали семейства выпуклых множеств тесно связаны с вопросами о покрытие произвольных множеств выпуклыми.

В. Кли1 показал, что для любого N существует семейство выпуклых мно жеств на плоскости такое, что для любых N из них существует 2-трансверсаль, но для всего семейства множеств такая трансверсаль не существует. Данный пример показывает, что в общем случае не существует прямого обобщения теоремы Хелли на случай k-трансверсали для произвольного семейства вы пуклых множеств. Поэтому следует накладывать ряд ограничений на рас сматриваемые семейства.

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

Л.Данцер и Б.Грюнбаум2 доказали, что при некоторых натуральных d и k существует аналог теоремы Хелли для семейства параллелепипедов с параллельными рёбрами в Ed. Они нашли все такие d и k, тем самым полно стью решив данную задачу. Также М. Качальский и Д. Наштир3 показали, что если любые девять треугольников из семейства гомотетов некоторого треугольника на плоскости имеют 2-трансверсаль, то всё семейство имеет 2-трансверсаль.

Г. Хадвигером и Г. Дебруннером4 была также поставлена следующая задача. Существует ли и чему равно число M(p, q, d) наименьшее нату ральное число такое, что если любое семейство P выпуклых компактных множеств в Ed, обладающее свойством, что любое его подсемейство из p эле Klee V. Письмо к P.Vincensini от 27 октября 1954г.

Danzer L., Grnbaum B. Intersection properties of boxes in Rd. // Combinatorica. 1982. Vol. 2, no. 3.

u Pp. 237–246.

Katchalski M., Nashtir D. On a conjecture of Danzer and Grnbaum // Proceedings of the American u Mathematical Society. 1996. Vol. 124, no. 10. Pp. 3213–3218.

Хадвигер Г., Дебруннер Г. Комбинаторная геометрия плоскости. 1965.

ментов имеет q элементов с непустым пересечением, то всё семейство P имеет M(p, q, d)-трансверсаль.

Ими было доказано, что M(p, q, d) p q + 1, а также равенство d M(p, q, d) = p q + 1, если d + 1 q (d + 1).

q p d Легко видеть, что если q d, то M(p, q, d) =.

d + 1 было доказано Существование чиcел M(p, q, d) для любых p q Н. Алоном и Д. Клейтманом. Полученные в этой работе оценки очень грубы.

Данные оценки можно существенно улучшить, если наложить ограниче ния на семейства рассматриваемых выпуклых компактных множеств. Р. Ка расёв6 показал, что M(2, 2, 2) = 3 для семейства транслятов выпуклой фигу ры на плоскости.



В диссертации получены некоторые точные значения M(p, q, 2) для се мейства равных кругов на плоскости.

Д. Фон-Дер-Флаас и А. Косточка7 уточнили верхнюю оценку на M(p, 2, d) для семейства параллелепипедов с параллельными рёбрами в Ed d1 d M(p, 2, d) (p 1) log2 (p 1) + d (p 1) log2 (p 1).

5p В этой же работе они показали, что M(p, 2, 2).

В диссертации улучшена верхняя оценка M(p, 2, d) для таких семейств.

Другой путь обобщения теорем типа Хелли предложили Л. Ловас и Alon N., Kleitman D. Piercing convex sets and the Hadwiger-Debrunner (p, q)-problem // Advances in Mathematics. 1992. Vol. 96, no. 1. Pp. 103–112.

Alon N., Kleitman D. A purely combinatorial proof of the Hadwiger Debrunner (p, q)-conjecture // Electr. J. Comb. 1997. Vol. 4, no. 2.

Karasev R. Transversals for families of translates of a two-dimensional convex compact set // Discrete and Computational Geometry. 2000. Vol. 24, no. 2. Pp. 345–354.

Fon-Der-Flaass D., Kostochka A. Covering boxes by points // Discrete Mathematics. 1993. Vol. 120, no. 1-3. Pp. 269–275.

И. Барани8. Они рассмотрели раскрашенные ( цветные ) версии клас сических теорем комбинаторной геометрии. В частности, доказали раскра шенную версию теоремы Хелли.

В данной работе доказывается раскрашенный вариант теоремы Юнга.

Вторая глава посвящена вопросам связанным с сжимающими отображе ниями, теоремой Киршбрауна и P L-изометриям.

Отображение одного метрического пространства в другое называется сжимающим, если оно не увеличивает расстояние между любыми двумя точ ками.

М. Киршбраун9 в 1934 году доказал, что для любого сжимающего отоб ражения : A Ed, где A Ed, существует такое сжимающее отображение : Ed Ed, что (x) = (x)|A.

Ф. Валентайн в серии работ10 рассмотрел несколько обобщений этой тео ремы, в частности, доказал её аналог для гиперболического пространства.

Другие доказательства теоремы Киршбрауна, а также их обобщения были получены E. Майклом11, И. Шёнбергом12, Б. Грюнбаумом13.

У. Ланг и В. Шрёдер14 доказали существование продолжения сжимаю Brny I. A generalization of Carathodory’s theorem //Discrete Mathematics. 1982. Vol. 40, no. 2-3.





aa e Pp. 141–152.

Kirszbraun M. Uber die zusammenziehenden und Lipschitzschen Transformationen // Fund. Math.

1934. Vol. 22. Pp. 77–108.

Valentine F. A. On the extension of a vector function so as to preserve a Lipschitz condition // Bulletin of the American Mathematical Society. 1943. Vol. 49. Pp. 100–108.

Valentine F. Contractions in non-Euclidean spaces // Bulletin (New Series) of the American Mathematical Society. 1944. Vol. 50, no. 10. Pp. 710–713.

Valentine F. A. A Lipschitz condition preserving extension for a vector function // American Journal of Mathematics. 1945. Vol. 67, no. 1. Pp. 83–93.

Mickle E. On the extension of a transformation // Bull. Amer. Math. Soc. 1949. Vol. 55. Pp. 160–164.

Schoenberg I. On a theorem of Kirzbraun and Valentine // American Mathematical Monthly. 1953.

Vol. 60, no. 9. Pp. 620–622.

Grnbaum B. A generalization of theorems of Kirszbraun and Minty // Proceedings of the American u Mathematical Society. 1962. Vol. 13, no. 5. Pp. 812–814.

Lang U., Schroeder V. Kirszbraun’s theorem and metric spaces of bounded curvature // Geom. Funct.

щего отображения между пространствами с ограниченной по Александрову кривизной.

Из теоремы Хелли сразу следует, что теорему Киршбрауна достаточно доказывать для таких множеств A, что |A| d + 1.

Определение 2.2. P L-изометрией называется P L-отображение, сохраняю щее длины всех кривых. Иначе говоря, если P1 и P2 полиэдральные простран ства (см. например15), то отображение : P1 P2 называется P L-изометрией, если ограничение на каждый симплекс некоторой локально конечной три ангуляции P1 есть изометрия.

Разные свойства P L-изометрии были исследованы в работе16 Дж. Ло уренса и Дж. Спингарта. В 1981-ом году У. Брем17 показал, что существует P L-изометрия, решающая задачу о продолжение Киршбрауна для конечного множества точек.

P L-изометрия может интерпретироваться как обобщение оригами. По этому классические задачи, связанные с оригами (см. например18), могут рас сматриваться как задачи о P L-изометрии. В работе было предложено реше ние известной задачи М. Гарднера19 об одном разрезе для P L-изометрий.

В третьей главе доказывается кусочно-линейный вариант знаменитой теоремы Нэша–Кейпера20 об аппроксимации гладкого вложения риманова Anal. 1997. Vol. 7, no. 3. Pp. 535–560.

Бураго Д. Ю., Бураго Ю. Д., Иванов С. В. Курс метрической геометрии. Ижевск: ИКИ, 2004.

Lawrence J., Spingarn J. An intrinsic characterization of Foldings of Euclidean Space. // Ann. Inst.

Henri Poincar, Analyse non linaire. 1989. Vol. S6. Pp. 365–383.

e e Brehm U. Extensions of distance reducing mappings to piecewise congruent mappings on Rm // Journal of Geometry. 1981. Vol. 16, no. 1. Pp. 187–193.

Тарасов А. C. Решение задачи Арнольда о мятом рубле // Чебышевский сборник. 2004. 5.

Т. 1, № 9.

Demaine E. D., Demaine M. L. Fold-and-Cut Magic // Tribute to a Mathemagician. A K Peters, 2004.

Pp. 23–30.

Гарднер М., Смородинский Я. А., Данилов Ю. А. Математические досуги Оникс М., 1995.

Нэш Дж. О C 1 -изометрических вложениях // Математика. 1957. Т. 1, № 2. С. 3 16.

многообразия в Ed гладким изометрическим вложением.

Естественными являются обобщения данной теоремы, где вместо глад ких изометрических вложений рассматривается более широкий класс отобра жений, сохраняющих длины кривых.

Для произвольных сжимающих отображений обобщение теоремы Нэша– Кейпера было получено М. Громовым21. Он доказал, что если M1 и M римановы многообразия, причём dim(M1) dim(M2), то любое сжимающее отображение f : M1 M2 можно аппроксимировать отображением :

M1 M2, сохраняющим длины всех кривых.

Ю. Д. Бураго и В. А. Залгаллер22 доказали кусочно-линейный вариант теоремы Неша–Кейпера для двумерных P L-многообразий.

С. Крат, А. Петрунин и Д. Бураго23 доказали кусочно-линейный вариант теоремы Громова, а именно показали, что любое сжимающее отображение f двумерного полиэдрального пространства P в E2 может быть аппроксими ровано P L-изометрией, то есть для любого 0 существует P L-изометрия : P E2, что d(f (x), (x)) для всех x из P.

В диссертации эта теорема обобщается для произвольных размерностей.

При доказательстве этого утверждения используются результаты второй гла вы о P L варианте теоремы Киршбрауна.

Как будет показано, данная задача связана с задачами о увеличении объ ёма многогранника. Д. Бликер24 первым заметил, что для любого тетраэдра Кейпер Н. Х. О C 1 -изометрических вложениях // Математика. 1957. Т. 1, № 2. С. 17–28.

Громов М. Дифференциальные соотношения с частными производными. 1990.

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

Krat S., Burago D., Petrunin A. Approximatings Short Maps by P L-isometies and Arnold’s “Can You Make Your Dollar Biegger” Problem.: Ph. D. thesis.

Bleecker D. Volume increasing isometric deformation of convex polyhedra // Journal of Dierential Geometry. 1996. Vol. 43, no. 3. Pp. 505–526.

существует невыпуклый многогранник, ограничивающий больший объём, по верхность которого изометрична (по внутренней метрике) поверхности тетра эдра. Пользуясь методом Бликера, Г. Самарин25 доказал аналогичное утвер ждение для всех выпуклых многогранников в трёхмерном пространстве. Од новременно этот результат был обобщён И. Паком26.

В работе доказаны ослабленная версия теоремы Бликера–Пака–Самари на для произвольных размерностей.

Цель работы 1. Получить новые оценки на мощность минимальной трансверсали для семейств параллелепипедов c параллельными рёбрами и семейства рав ных кругов. Доказать существование разбиения множества в метриче ском пространстве с ограниченной суммой диаметров частей. Получить обобщение теоремы Юнга на случай покрытия множеств несколькими шарами, а также раскрашенную теорему Юнга.

2. Доказать ряд свойств P L-изометрии в гиперболических пространствах.

Дать конструктивное доказательство теоремы Киршбрауна для случая конечного числа точек в гиперболическом пространстве.

3. Применить разработанную в диссертации технику для доказательства дискретного аналога теоремы Нэша–Кейпера. Доказать, что для любо го выпуклого многогранника существует кусочно-линейно изометрич ный ему псевдомногогранник большего объёма.

Samarin G. A. Volume increasing isometric deformations of polyhedra // Computational Mathematics and Mathematical Physics. 2010. Vol. 50, no. 1. Pp. 54–64.

Pak I. Inating polyhedral surfaces // preprint. 2006.

Основные методы исследования В первой главе диссертации используются классические методы дискрет ной, метрической и выпуклой геометрии и теории графов.

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

Научная новизна Основные результаты диссертации являются новыми и состоят в следу ющем:

1. Улучшена оценка на мощность трансверсали для семейства параллеле пипедов в Ed таких, что среди любых p из них два имеют не пустое пе ресечение или, другими словами, любые p имеют (p 1)-трансверсаль.

Усилины оценки на мощность трансверсали семейства равных кругов на плоскости.

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

3. Дано конструктивное доказательство теоремы Киршбрауна для конеч ного множества точек в пространстве Лобачевского. Найдены след ствия из этой теоремы.

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

Теоретическая и практическая ценность Диссертация имеет теоретический характер.

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

Результаты второй и третьей главы диссертации могут быть использова ны при исследовании сжимающих отображений P L и римановых многообра зий, а также в теории многогранников.

Апробация результатов Основные результаты диссертации неоднократно докладывались на семи наре Дискретная геометрия и геометрия чисел под руководством Н. П. Дол билина, Н. Г. Мощевитина и М. Д. Ковалёва (мех-мат МГУ, 2006-2009 гг.);

На семинаре Арифметика и геометрия под руководством Н. Г. Мощевитина и А. М. Райгородского (мех-мат МГУ, 2006 г.);

На геометрическом семинаре под руководством И. Х. Сабитова и В. Ю. Протасова (МЦМНО, 2007-2010гг.);

На геометрическом семинаре ПОМИ РАН им. А. Д. Александрова под руко водством Ю. Д. Бураго (ПОМИ РАН, 2008 г.).

Также результаты диссертации докладывались на следующих междуна родных конференциях и семинарах: IX Международный семинар Дискрет ная математика и её приложения, посвящённый 75-летию со дня рожде ния академика О.Б. Лупанова, Москва (2007);

Mathematics research seminar, UTB, Brownsville, USA (2009-2010);

Combinatoire Algbrique et Gomtrique, e ee Paris, France (2009);

Workshop on Combinatorial Geometry and Topology, South Padre Island, USA (2009-2010);

Workshop “Voronoi-2008” Honoring 140th anniversary of G. F. Voronoi “Numerical geometry, grid generation and scientic computing”, Москва (2008);

The 17th Annual Meeting of the South Texas Mathematics Consortium, Edinburg, USA (2009);

“Geometry, Topology, Algebra and Number Theory Applications” dedicated to the 120th anniversary of Boris Delone, Москва (2010).

Публикации Основные результаты диссертации опубликованы в пяти работах, из них три в журналах из перечня ВАК. Список работ приведён в конце авторефе рата [1-5].

Структура диссертации Диссертация состоит из введения, трёх глав и списка используемых ис точников. Полный объём диссертации 75 страниц, библиография включает 47 наименований.

Краткое содержание работы Во введении даётся обзор результатов по теме диссертации и формули руются основные результаты работы.

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

Определение 1.2. Точки x, y в метрическом пространстве M назовём d-близ кими, если d(x, y) d. Будем говорить, что множество V в M (|V| p) об ладает (p, q, d)-свойством, если среди любых p точек множества V найдутся q попарно d-близких.

Наиболее важным результатом первого параграфа является следующая теорема.

Теорема 1.5. Если множество V обладает (p, q, d)-свойством, то его мож d[ p1 ].

но разбить на p 1 частей с суммой диаметров q Эта теорема имеет несколько следствий.

По теореме Юнга любое множество диаметра d в En может быть покрыто n шаром радиуса d ·. Поэтому верно следующее следствие теоремы 1.5.

2(n+1) Следствие 1.6. Пусть множество V в En обладает (p, q, d)-свойством.

Тогда V можно покрыть p 1 шарами с суммой радиусов d[ p1 ] · n.

2(n+1) q Кроме того, каждое множество диаметра d в евклидовом пространстве можно покрыть кубом c рёбрами равными d и параллельными осям коорди нат. Значит, верно следующее утверждение.

Следствие 1.7. Если множество V в En обладает (p, q, d)-свойством, то V можно покрыть p 1 кубами с суммой длин рёбер d[ p1 ], рёбра которых q параллельны осям координат.

Если рассмотреть граф со стандартной псевдометрикой, то можно полу чить следующее следствие теоремы 1.5.

Следствие 1.8. Если в конечном графе из любых p вершин можно выбрать q-клику, то граф можно разбить на не более чем p 1 подграфов с суммой диаметров (по внутренней метрике частей) не большей чем [ p1 ].

q Получены усиления теоремы 1.5 для связных множеств в евклидовом пространстве или множеств, у которых каждая точка является предельной.

Второй и третий параграф посвящён частным случаем задачи Хадвигера и Дебруннера о M(p, q, d)-трансверсали.

Во втором параграфе рассматриваются задача о покрытии кругами мно жеств на плоскости и двойственная ей задача о поиске конечной трансверсали для множества равных кругов.

Определение 1.5. Будем говорить, что множество V ( |V| p) в метриче ском пространстве M обладает (p, q)r -свойством, если любые p точек этого множества можно покрыть q шарами радиуса r.

Доказаны следующие две теоремы и их следствия. Теорема 1.12 даёт ответ на вопрос Б. Грюнбаума27.

Теорема 1.12. Если V E2 обладает (4, 2)r -свойством, то его можно покрыть 4-мя кругами радиуса r. Данное число кругов является наимень шим.

Отметим, что Б. Грюнбаум предполагал, что наименьшее число кругов в данном случае равно 6.

Следствие 1.13. Пусть в E2 дано семейство равных кругов, обладающее свойством, что для любые четыре из них имеют 2-трансверсаль. Тогда всё семейство имеет 4-трансверсаль.

Теорема 1.14. Если V E2 обладает (3, 2)r-свойством, то его можно по крыть 6-ю кругами радиуса r. Данное число кругов является наименьшим.

Следствие 1.15. Пусть в E2 дано семейство равных кругов, что из любых трёх из них два пересекаются. Тогда всё семейство имеет 6-трансверсаль.

Также в этом параграфе уточнён контрпример В. Кли к обобщению тео ремы Хелли для k-трансверсали, при k 1.

Теорема 1.16 Для любого N существует семейство из N + 1 выпуклого множества на плоскости такое, что для любых N множеств из этого се мейства существует 2-трансверсаль, но для всего семейства 2-трансверсали не существует.

Заметим, что пример В. Кли приводится только для чётных N.

В третьем параграфе улучшается оценка на число M(p, 2, d) для семей ства параллелепипедов с параллельными рёбрами.

Теорема 1.21. Пусть h(p) = p log 9 p + p. Тогда:

M(p, 2, 2) h(p 1).

Данцер Л., Грюнбаум Б., Кли В. Теорема Хелли // М: Мир. 1968. стр. 104.

Теорема 1.22.

d M(p, 2, d) (log 9 2 + o(1))p log2 p.

В четвёртом параграфе изучаются d-близкие множества.

Определение 1.6. Два непустых множества V1 и V2 в метрическом про странстве M назовём d-близкими, если d(x, y) d для любых x V1 и y V2.

Доказана следующая теорема, которую можно назвать раскрашенной теоремой Юнга.

Теорема 1.23. Если в пространстве En задано семейство из k 1 попарно d-близких множеств V1, V2,..., Vk, то одно из множеств можно покрыть кругом радиуса R, где R = d 2, если k n;

n 2(n+1), если k n.

R =d· Причём оценка на R является точной.

Обобщения теоремы Юнга для сферического пространства и простран ства Лобачевского исследовались в работах Ю. Д. Бураго28 и Б. В. Дексте ра29. В диссертации доказаны раскрашенные версии теоремы Юнга для этих пространств. Для пространства Лобачевского Hn :

ch R = ch2 d, если k d;

2n sh d, если k d.

sh R = (n+1) Для случая множеств в Sn, лежащих внутри некоторой фиксированной единичной полусфере соответствующие радиусы равны:

Бураго Ю. Д. Задача о круге Юнга для сферы // Математическое просвещение. № 6.С. 165–169.

Dekster B. V. The Jung theorem for spherical and hyperbolic spaces // Acta Mathematica Hungarica.

1995. Vol. 67, no. 4. Pp. 315–331.

cos R = cos2 d, если k d;

2n sin d, если k d.

sin R = (n+1) Очевидно, что если дано несколько попарно d-близких множеств, то диа метр каждого из них не превосходит 2d. Интересно оценить наименьший из диаметров этих множеств. Оказалось, что данная задача равносильна извест ной задаче о поиске оптимального антиподального кода.

Определение 1.7. Сферическим кодом называется любое конечное множе ство различных точек сферы Sn. Сферический код назовём антиподальным, если он симметричен относительно центра сферы.

Сферический код W из m точек называется оптимальным, если он об ладает максимальным минимальным диаметром (min dE (x, y), где x, y W и x = y) среди всех сферических кодов мощности m.

Через Dn (k) будем обозначать минимальный диаметр оптимального ан типодального кода мощности 2k на единичной сфере Sn1.

Теорема 1.25. Если в пространстве En задано семейство из k 1 по парно d-близких множеств V1, V2,..., Vk, то диаметр одного из них не превосходит 2d D=.

4 Dn (k) Причём оценка на D является точной.

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

Наглядным примером P L-изометрии служит отображение, переводящие обычный лист бумаги в фигуру оригами. Однако, не всегда P L-изометрия листа бумаги может быть реализована как оригами.

В первом параграфе приводятся различные примеры двумерных P L-изо метрии и обсуждаются вопросы о том, когда P L-изометрия является орига ми, а когда нет.

Во втором параграфе доказывается ряд теорем о P L-изометрии.

Назовём политопом пересечение конечного числа полупространств.

В начале параграфа показывается, что P L-изометрия пространства мо жет рассматриваться, как разрезание данного пространства на выпуклые по литопы, называемых листами, на каждом из которых P L-изометрия явля ется некоторым движением, причём для каждого политопа движения отли чаются.

Следующие две теоремы 2.1 и 2.2 для Ed доказали30 Дж. Лоуренс и Дж. Спингарт. В диссертации найдено более короткое и наглядное доказа тельство этих теорем, что даёт возможность перенести их на пространства Sd и Hd. Обозначим через X одно из пространств Ed, Sd и Hd.

Теорема 2.1. Локально конечное разбиение политопа P из X на листы яв ляется P L-изометрией тогда и только тогда, когда любая грань коразмер ности 2, принадлежит чётному числу листов, причём альтерированная сумма двумерных углов (то есть, соседние углы входят в сумму с разными знаками) при этой грани равна 0.

Теорема 2.2. Отображение : P X является P L-изометрией тогда и только тогда, когда выполнено следующее требование:

x P, r(x), y B(x, r(x))31 верно d(x, y) = d((x), (y)).

В третьем параграфе приводится доказательство P L-варианта теоремы Киршбрауна, а также некоторых следствий из этой теоремы.

Теорема 2.5. Пусть в пространстве X даны два конечных множества то чек A = {a1, a2,..., an } и B = {b1, b2,..., bn}, причём для любых различных Lawrence J., Spingarn J. An intrinsic characterization of Foldings of Euclidean Space. // Ann. Inst.

Henri Poincar, Analyse non linaire. 1989. Vol. S6. Pp. 365–383.

e e Здесь, через B(x, r(x)) обозначается шар с центром в x и радиуса r(x).

i и j верно d(ai, aj ) d(bi, bj ). Тогда существует P L-изометрия : X X такая, что (ai) = bi.

Как оказалось, полученная конструкция P L-изометрии в теореме 2.5 во многом похожа на конструкцию У. Брема17. Но техника, предложенная авто ром, в отличии от конструкции Брема, также работает и для пространства Лобачевского.

Следствие 2.6. Пусть в пространстве En или Hn даны два конечных мно жества точек A = {a1, a2,..., an } и B = {b1, b2,..., bn}, такие, что для любых i и j выполнено d(ai, aj ) d(bi, bj ). Тогда существует такая точ ка p, что для любого i, выполнено:

d(p, ai) d(p, bi).

Назовём кусочно-линейной фигурой ограниченное множество на плоско сти, граница которого является конечным объединением непересекающихся и несамопересекающихся замкнутых ломаных.

C помощью теоремы 2.5 можно легко получить решение задачи М. Гард нера19 об одном разрезе в классе P L-изометрий. Неформально её можно сформулировать так: для любой наперёд заданной кусочно-линейной фигуры на листе бумаге, существует сгибание этого листа, такое что данная фигура может быть вырезана одним прямолинейным надрезом ножницами.

Теорема 2.7. Для любой кусочно-линейной фигуры существует P L-изо метрия такая, что границы фигуры отображаются на одну прямую, кроме того эта прямая не пересекает образ внутренностей фигуры.

В третьей главе доказывается кусочно-линейный аналог теоремы Нэша– Кейпера. В первом параграфе даются необходимые определения, формули ровки и приводятся следствия основной теоремы. Во втором параграфе эта Brehm U. Extensions of distance reducing mappings to piecewise congruent mappings on Rm // Journal of Geometry. 1981. Vol. 16, no. 1. Pp. 187–193.

Гарднер М., Смородинский Я. А., Данилов Ю. А. Математические досуги. Оникс М., 1995.

теорема доказывается для случая евклидовых полиэдральных пространств.

В третьем параграфе приводится аналог этого результата для сферических и гиперболических полиэдральных пространств.

Основным результатом этой главы является следующая теорема.

конечное32 d-мерное евклидово полиэдральное Теорема 3.7. Пусть P пространство, отображение f : P En (n d) является сжимающим.

Тогда для любого 0 существует P L-изометрия : P En такая, что d(f (x), (x)) для любой точки x из P.

Теоремы 3.18 и 3.17 обобщают этот результат для сферических и гипер болических полиэдральных пространств.

Назовём псевдомногогранником образ P L-многообразия гомеоморфного сфере при P L-отображении в Ed. Назовём его объёмом, объём множества точек, которые находятся в разных компонентах связности с бесконечно уда лённой точкой.

Теорема 3.11. Для любого выпуклого многогранника P в пространстве Ed существует псевдомногогранник P, ограничивающая больший объём чем P, такой, что поверхность P изометрична поверхности P.

Данная теорема является прямым следствием теоремы 3.7 и теоремы И.Пака26 о существовании поверхности изометричной поверхности выпуклого многогранника P и, ограничивающей объём больший чем P.

Публикации автора по теме диссертации 1. Akopyan A. V., Tarasov A. S. PL-analogue for Nash–Kuiper theorem. // Numerical geometry, grid generation and scientic computing. Special event:

Workshop “Voronoi-2008”. Honoring 140th anniversary of G.F. Voronoi / то есть cответствующий комплекс состоит из конечного числа многогранников.

Pak I. Inating polyhedral surfaces // preprint. 2006.

Ed. by V. Garangza, Y. G. Evtushenko, N. Weatherill. Издательство Фолиум, 2008.

В данной работе А.С. Тарасову принадлежит постановка задачи. Доказательство основных результатов принадлежит А.В. Акопяну.

2. Акопян А. В. O пересечении параллелепипедов в Rd // Математические заметки. 2008. Т. 83, № 1. С. 153–156.

3. Акопян А. В., Дольников В. Л. Некоторые обобщения диаметра мно жества и задача Юнга // Моделирование и Анализ Информационных Систем. 2006. Т. 13. С. 66–70.

В данной работе В.Л.Дольникову принадлежит постановка задачи. Доказательство основных результатов принадлежит А.В. Акопяну.

4. Акопян А. В., Тарасов А. С. О складывании бумаги, переводящее одно заданное множество точек в другое // Материалы IX Международного семинара ДИСКРЕТНАЯ МАТЕМАТИКА И ЕЁ ПРИЛОЖЕНИЯ по свящённого 75-летию со дня рождения академика О.Б. ЛУПАНОВА.

2007. С. 362–363.

В данной работе А.С. Тарасову принадлежит постановка задачи. Доказательство основного результата принадлежит А.В. Акопяну.

5. Акопян А. В., Тарасов А. С. Конструктивное доказательство теоремы Киршбрауна // Математические заметки. 2008. Т. 84, № 5. С. 781–784.

В данной работе А.С. Тарасову принадлежит постановка задачи. Доказательство основного результата принадлежит А.В. Акопяну.



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.