Оглавление
- 1 Выпуклый корпус
- 1.1 Определение выпуклой оболочки
- 1.2 Визуализация и топологические свойства
- 1.3 Экстремальные точки и компактные множества
- 1.4 Оператор выпуклой оболочки
- 1.5 Алгоритмические задачи
- 1.6 Применение и связанные структуры
- 1.7 Выпуклая оболочка конечного множества точек
- 1.8 Симплициальные многогранники
- 1.9 Простые многоугольники
- 1.10 Броуновское движение
- 1.11 Пространственные кривые
- 1.12 Функции
- 1.13 Вычисление выпуклой оболочки
- 1.14 Связанные структуры
- 1.15 Приложения
- 1.16 Многоугольники Ньютона и многогранники Ньютона
- 1.17 Теорема Гаусса–Лукаса
- 1.18 Спектральный анализ
- 1.19 Теорема Руссо–Дай
- 1.20 Дискретная геометрия
- 1.21 Гиперболические выпуклые оболочки
- 1.22 Статистика
- 1.23 Комбинаторная оптимизация
- 1.24 Экономика
- 1.25 Геометрическое моделирование
- 1.26 Этология
- 1.27 Квантовая физика
- 1.28 Термодинамика
- 1.29 История
- 1.30 Полный текст статьи:
- 2 Выпуклая оболочка
Выпуклый корпус
-
Определение выпуклой оболочки
- Выпуклая оболочка фигуры — это наименьшее выпуклое множество, содержащее её.
- Определяется как пересечение всех выпуклых множеств, содержащих данное подмножество.
- Эквивалентна множеству всех выпуклых комбинаций точек в подмножестве.
-
Визуализация и топологические свойства
- Визуализируется как форма, окруженная резиновой лентой.
- Замкнутые выпуклые оболочки — это замыкания выпуклых оболочек.
- Открытые выпуклые оболочки — это внутренние части выпуклых оболочек.
-
Экстремальные точки и компактные множества
- Крайние точки выпуклого множества не лежат на открытых отрезках между другими точками.
- Каждое компактное выпуклое множество является выпуклой оболочкой своих крайних точек.
-
Оператор выпуклой оболочки
- Оператор выпуклой оболочки обладает свойствами оператора замыкания.
- Применяется для представления антиматроидов.
-
Алгоритмические задачи
- Нахождение выпуклой оболочки конечного множества точек решается за время O(n log n) для двух- и трехмерных наборов точек.
- В более высоких измерениях сложность ограничена теоремой о верхней границе.
-
Применение и связанные структуры
- Выпуклые оболочки используются в математике, статистике, комбинаторной оптимизации и экономике.
- Связанные структуры включают ортогональную выпуклую оболочку, выпуклые слои и триангуляцию Делоне.
-
Выпуклая оболочка конечного множества точек
- Образует выпуклый многоугольник в двух измерениях или выпуклый многогранник в общем случае.
- Каждая крайняя точка оболочки называется вершиной.
- Выпуклая оболочка включает в себя все точки множества.
-
Симплициальные многогранники
- Для множеств точек в общем положении выпуклая оболочка является симплициальным многогранником.
- Число граней выпуклой оболочки в d-мерном пространстве равно O(n^(d/2)).
-
Простые многоугольники
- Выпуклая оболочка простого многоугольника делит его на области, включая сам многоугольник.
- Рекурсивное вычисление декомпозиции формирует дерево выпуклых различий.
-
Броуновское движение
- Кривая броуновского движения имеет выпуклую оболочку, граница которой образует непрерывно дифференцируемую кривую.
- Размерность Хаусдорфа набора исключительных моментов времени равна 1 – π/2θ.
-
Пространственные кривые
- Части границы выпуклой оболочки пространственной кривой являются развертываемыми и линейчатыми поверхностями.
- Примеры: олоид, сферикон, D-формы.
-
Функции
- Выпуклая оболочка функции f является функцией, эпиграфом которой является нижняя выпуклая оболочка эпиграфа f.
- Это единственная максимальная выпуклая функция, определяемая f.
-
Вычисление выпуклой оболочки
- В вычислительной геометрии известны алгоритмы для вычисления выпуклой оболочки.
- Сложность алгоритмов зависит от количества входных точек и точек на выпуклой оболочке.
- Для двух и трех измерений известны алгоритмы, чувствительные к выходным данным.
-
Связанные структуры
- Аффинная оболочка, линейная оболочка, коническая оболочка, визуальная оболочка, круговая оболочка, относительная выпуклость, ортогональная выпуклая оболочка, гипервыпуклая оболочка, голоморфно выпуклая оболочка.
- Триангуляция Делоне и диаграмма Вороного связаны с выпуклыми оболочками.
- Альфа-формы и выпуклые слои множества точек.
-
Приложения
- Выпуклые оболочки используются в математике, статистике, экономике, геометрическом моделировании и изучении поведения животных.
-
Многоугольники Ньютона и многогранники Ньютона
- Выпуклые оболочки точек, полученных из показателей степени членов многочлена
- Используются для анализа асимптотического поведения многочлена и вычисления его корней
-
Теорема Гаусса–Лукаса
- Все корни производной многочлена лежат внутри выпуклой оболочки корней многочлена
-
Спектральный анализ
- Числовой диапазон нормальной матрицы представляет собой выпуклую оболочку ее собственных значений
-
Теорема Руссо–Дай
- Описывает выпуклые оболочки унитарных элементов в C*-алгебре
-
Дискретная геометрия
- Теорема Радона и теорема Тверберга касаются существования разбиений точечных множеств на подмножества с пересекающимися выпуклыми оболочками
-
Гиперболические выпуклые оболочки
- Используются в гипотезе геометризации в низкоразмерной топологии
- Применяются для расчета канонических триангуляций гиперболических многообразий
-
Статистика
- Выпуклая оболочка является ключевым компонентом bagplot
- Контуры глубины Тьюки образуют вложенное семейство выпуклых множеств
-
Комбинаторная оптимизация
- Центральные объекты изучения – выпуклые оболочки индикаторных векторов решений
- Используются алгоритмы, основанные на линейном программировании
-
Экономика
- В модели Эрроу–Дебре предполагается выпуклость бюджетных наборов и предпочтений
- Теорема Шепли–Фолкмана используется для доказательства существования равновесия
-
Геометрическое моделирование
- Кривая Безье лежит внутри выпуклой оболочки своих контрольных точек
- Используется для быстрого обнаружения пересечений кривых
-
Этология
- Выпуклая оболочка используется для оценки ареала обитания животных
- Выбросы могут сделать минимальный выпуклый многоугольник чрезмерно большим
-
Квантовая физика
- Пространство состояний квантовой системы представляет собой выпуклую оболочку
- Теорема Шредингера–ХЬЮ доказывает, что смешанное состояние можно записать как выпуклая комбинация чистых состояний
-
Термодинамика
- Выпуклая оболочка определена Джозайей Уиллардом Гиббсом
- Стабильные измерения выполняются на нижней выпуклой оболочке
-
История
- Термин “выпуклая оболочка” появился в 1935 году
- В 1938 году термин “выпуклый корпус” стал стандартным