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

• Автор: Карасёв, Роман Николаевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Долгопрудный
• Количество страниц: 86 с.

Оглавление
Введение

Некоторые обозначения

1 О трансверсалях семейства транслятов двумерного выпуклого компакта

1.1 Формулировка результата

1.2 Вспомогательные факты

1.3 Доказательство основной теоремы

2 М-сильная выпуклость и порождающие множества

2.1 Введение

2.2 Вспомогательные факты

2.3 Доказательство теоремы 2.

2.4 Применение теоремы 2.
2.5 Эквивалентность М-сильной выпуклости и М-выпуклости
2.6 Доказательство аналога теоремы Каратеодори
2.6.1 Сведение доказательства к лемме 2.
2.6.2 Доказательство леммы 2.23
2.7 Тела постоянной ширины
2.7.1 Основные понятия и результаты
2.7.2 Доказательства
3 О назначении точек гиперграням многогранника
3.1 Введение
3.2 Формулировка основных результатов
3.3 Вспомогательные утверждения
3.4 Доказательства основных результатов
3.5 Следствия доказанных теорем
Литература

Введение
Интерес к исследованиям в области дискретной геометрии и выпуклого анализа в последние десятилетия вызван значительным прогрессом в развитии вычислительной техники, который сделал возможным решение разнообразных задач геометрической оптимизации и управления и привел к постановке многих новых задач в этой области. Классическими задачами оптимизации в дискретной геометрии являются покрытия, упаковки и выпуклые разбиения, несколько результатов в этой области приведены в данной работе.
Задачи управляемости и наблюдаемости в математической теории оптимального управления сводятся к изучению “множеств достижимости”, которые для некоторых классов задач являются выпуклыми множествами. В частности, некоторые задачи математической теории оптимального управления и теории дифференциальных игр требуют изучения свойств выпуклых множеств (выпуклый анализ) и возможных усилений понятия выпуклого множества. Последнему вопросу посвящена глава 2 данной работы.
Одним из фундаментальных результатов выпуклого анализа является теорема Хелли (см. [2]). Она утверждает, что конечное семейство выпуклых множеств в К имеет непустое пересечение тогда и только тогда, когда любое подсемейство из не более чем п + 1 множества имеет непустое пересечение. В книге Л. Данцера, Б. Грюнбаума и В. Кли [2] содержатся разные приложения теоремы Хелли и ее обобщения, в частности, топологическая теорема Хелли, которая утверждает, что в теореме Хелли достаточно вместо выпуклости требовать гомологической тривиальности всех множеств семейства и всех их непустых пересечений.
Один из путей обобщения теоремы Хелли связан с понятием к-транс-версали семейства множеств — такого множества из к точек, которое пересекается с любым множеством семейства. Теорема Хелли утверждает, что конечное семейство выпуклых множеств имеет 1-трансвер-саль тогда и только тогда, когда 1-трансверсаль имеет любое подсемейство из не более чем п + 1 элемента.
Однако, для А-трансверсалей при к > 2 аналог теоремы Хелли не верен ни при какой константе вместо п +1. Тем не менее (см. обзор [4])

ВВЕДЕНИЕ

при рассмотрении других классов семейств аналогичные результаты могут быть установлены. Кроме того, в аналогах теоремы Хелли можно требовать выполнение более сильных условий, чем существование к-трансверсали достаточно малых подсемейств. В частности, Б. Грюнбау-мом была сформулирована гипотеза о том, что семейство транслятов выпуклого компакта на плоскости имеет 3-трансверсаль, если любые два множества из этого семейства пересекаются.
Ранее в литературе приводились частичные доказательства этой гипотезы в случае евклидовых кругов [5, 6], треугольников [7], центрально симметричных множеств [8] или множеств постоянной ширины [9].
Глава 1 посвящена полному доказательству гипотезы Грюнбаума. В процессе доказательства установлено, что эта гипотеза допускает переформулировку в терминах покрытий одного выпуклого множества транслятами другого, поэтому она аналогична вопросу о количестве частей меньшего диаметра, на которые можно разрезать выпуклое множество в К" (задача Борсука), а также вопросу о количестве гомотети-чески уменьшенных копий, необходимых для покрытия фигуры заданного выпуклого множества (задача Хадвигера).
В главе 2 излагается ряд результатов, связанных с понятием М-силъной выпуклости и порождающего множества.
Понятия сильной выпуклости возникло как некоторое усиление понятия строгой выпуклости. Сильно выпуклые множества с радиусом R, то есть множества, образованные пересечением шаров радиуса Д, использовались в работах Б.Т. Поляка, A. Plis, М.А. Красносельского и A.B. Покровского в приложении к задачам оптимизации.
В работе H. FrankowskaH Cli. Olech [16] подробно изучались свойства сильно выпуклых множеств радиуса R, были установлены критерии сильной выпуклости в терминах опорной функции и доказано утверждение, что множество является сильно выпуклом радиуса R тогда и только тогда, когда вместе с любыми двумя точками оно содержит любую дугу радиуса R и длины не более irR с концами в этих точках.
В работах Е.С. Половинкина (см. [13]) были установлены новые свойства сильной выпуклости, были доказаны аналоги теорем Крейна-Мильмана и Каратеодори в конечномерных пространствах и исследованы сильно выпуклые аппроксимации множеств и функций. Эти результаты позволили Г.Е. Иванову и Е.С. Половинкину в [12] получить новые алгоритмы второго порядка в теории дифференциальных игр.
Е.С. Половинкин ввел понятие М-сильно выпуклого множества, где М — любое замкнутое выпуклое множество: М-сильно выпуклым множеством называется любое пересечение транслятов М. При этом оказалось, что результаты о сильной выпуклости радиуса R можно перенести на М-сильную выпуклость только тогда, когда множество М удовлетворяет одному дополнительному условию: для любого М-сильно выпуклого множества А найдется множество В такое, что А + В — М
М-СИЛЬНАЯ ВЫПУКЛОСТЬ

Доказательство при intF = 0. Так как для любого Y = П{€т(-ЛТ + t), такого, что intF ф 0 найдется F* такое, что Y -f Y* = М, то по лемме 2.18 множество М — порождающее. □
2.4 Применение теоремы 2.
Покажем, как с помощью теоремы 2.3 можно доказать некоторые известные утверждения (см. [15]).
Теорема 2.19. Шары в гильбертовых пространствах являются порождающими множествами.
Доказательство. Пусть X — единичный шар в некотором гильбертовом пространстве. По теореме 2.3 достаточно проверить определение порождающего множества для множеств Y, являющихся пересечениями двух шаров. По лемме 2.1.8 можно считать, что intF ф 0.
Возьмем произвольную точку х £ bdX и явно найдем транслят F, содержащий х и содержащийся в X. Пусть единичный вектор внешней нормали в х равен п и найдем точку у £ F, у которой такой же вектор нормали.
Теперь сдвинем F так, чтобы точка у совпала с х. При этом по лемме 2.9, которая утверждает, что
NX(Y) = АЦХ + h) + N„{X + t2),
вектор п представляется в виде п — ащ + ßn2.
Если при этом один из векторов ani и ßn2 равен нулю, то получим,
что п = п 1 или п = п2. Это означает, что X совпадает с соответствую-
щим X + 1г. Б этом случае F лежит в X.
Рассмотрим случай, когда а ж ß не равны нулю. Заметим, что из выпуклости единичного шара следует, что а + ß > 1.
Тогда множество X задается неравенством
X = {а/: (х' — х, Д — ж) -+■ 2(ге, х’ — х) < 0},
так как это единичный шар, нормаль которого известна. Аналогично, множество точек х' € Y задано системой
Г (х1 — х,х' — х) + 2(пх, х' — х) < 0 (х1 — х,х' — х) + 2(n2,х1 — х) < 0.
Теперь, если какая-то точка х1 находится в F, то сложив оба неравенства системы, определяющей Y, предварительно умножив их на а и ß найдем, что
(а + ß){x‘ — х, х' — х) + 2(п,х' — х) < 0,