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

• Автор: Акопян, Арсений Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 75 с. : ил.

ОГЛАВЛЕНИЕ

Используемые обозначения

Введение

ГЛАВА 1. Разбиение п покрытие множеств с общими ограничениями

1.1. Разбиение на части с ограниченным суммарным диаметром

1.2. О покрытии кругами множеств с (р, 2)^-свойствами

1.3. О трансверсалях семейства параллелепипедов с параллельными рёбрами

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

ГЛАВА 2. РЬ-изометрпи

2.1. Определения и основные свойства
2.2. РР-изометрпя в классических однородных пространствах
2.3. Кусочно-линейный аналог теоремы Киршбрауна
ГЛАВА 3. РР-аналог теоремы Нэша-Кейпера
3.1. Формулировки основных результатов
3.2. Доказательство для евклидовых полиэдральных пространств
3.3. Случаи полиэдральных пространств постоянной кривизны
Список использованных источников

ИСПОЛЬЗУЕМЫЕ ОБОЗНАЧЕНИЯ
1. сопу V — выпуклая оболочка множества V.
2. с1 V — замыкание множества V.
3. пгЬУ — внутренность множества V.
4. Ьс1 V — граница множества V.
5. (1м{х,у) — расстояние между точками х и у в метрическом пространстве М. Обычно указывается без индекса, если понятно о каком про-
странстве идёт речь.
6. сПтАЛ - размерность пространства АЛ.
7. сПат V — диаметр множества V.
8. 5(:к, г) сфера с центром в точке х п радиуса г.
В{х, г) — шар с центром в точке :г п радиуса г.
9. Е — ^-мерное евклидово пространство.
10. — ^-мерная единичная сфера.
11. пространство Лобачевского размерности с1 и кривизной —1.
12. [;с] — целая часть числа х.
13. ргф — ортогональная проекция на Ь.

ВВЕДЕНИЕ
Данная диссертация посвящена задачам о существовании конечных ' трансверсалей у семейств множеств. Работа состоит из трёх глав.
В первой главе исследуются такие классические вопросы дискретной геометрии, как существование трансверсали семейства выпуклых множеств и покрытия множеств кругами или транслятамн выпуклого тела.
Во второй главе рассматриваются вопросы, связанные с РД-нзометрпей, то есть кусочно-линейным отображением, сохраняющем длины всех кривых. Также доказывается кусочно-линейный аналог теоремы Кнршбрауна, о продолжении сжимающего отображения. Теорема Кнршбрауна тесно связана с теоремой Хеллп, то есть с существованием 1-трансверсалп у семейства шаров.
В третьей главе доказан кусочно-линейный аналог теоремы Нэша-Кеппера. Этот вариант теоремы можно интерпретировать, как существование конечной трансверсали для семейства шаров в метрических пространствах специального вида.
Напомним формулировку классической теоремы Хелли. Здесь и далее через Е<; будем обозначать d-мерное евклидово пространство.
Теорема Хелли. Если & семейство выпуклых компактных множеств в Ef/ такое, что пересечение любых d + 1 из них не пусто, то пересечение всех множеств из 0й не пусто.
Естественным является следующий вопрос: каким требованиям должно удовлетворять семейство множеств, чтобы его можно было разбить на к частей, каждая из которых имеет непустое пересечение. В этом случае, множество из к точек «протыкающих» (piercing) всё множество называют А-трансверсалыо.
Вопросы о существовании А-трансверсалп семейства выпуклых множеств тесно связаны с вопросами о покрытие произвольных множеств выпуклыми.
В. Клн [22] показал, что для любого N существует семейство выпук-

Замечание 1.24.1. Легко видеть, что из дайной теоремы следует, что при к ^ п все кроме, быть может, одного множества Vi можно покрыть шаром радиуса djл/2. При к > п шаром радиуса d ■ уурррту можно покрыть все множества Vi, кроме каких-то п из них.
Замечание 1.24.2. Используя обобщения теоремы Юнга для сферического пространства и пространства Лобачевского, полученные в работах [8] и [36], можно получить аналог теоремы 1.23 в этих пространствах.
Без изменений доказательство проходит в пространстве Лобачевского Н'!. В этом случае имеем:
ch R = ch2 d, если к ^ d; sh R = у рГ+Т) sh щ если к > d.
Для множеств в §'!, лежащих внутри некоторой фиксированной единичной полусферы, соответствующие радиусы равны:
cos R = cos2 d, если к ^ d sin R — у/sin I, если к > d.
Следующие теоремы посвящены второму вопросу.
Определение 1.7. Сферическим кодом называется любое конечное множество различных точек сферы §". Сферический код назовем антиподалъньш, если он симметричен относительно центра сферы.
Сферический код W из т точек называется оптимальным, если он обладает максимальным минимальным диаметром (min Фе(ж, у), где х,у е W и х / у) среди всех сферических кодов мощности т.
Через Dn(k) будем обозначать минимальный диаметр оптимального ан-типодальпого кода мощности 2к на единичной сфере §"~1.