Введение

Наименьшее выпуклое множество, содержащее данное множество, и наименьшая выпуклая форма, заключающая данную форму. В геометрии выпуклая оболочка, выпуклый слой или выпуклое замыкание фигуры — это наименьшее выпуклое множество, содержащее её. Выпуклая оболочка может быть определена как пересечение всех выпуклых множеств, содержащих данное подмножество евклидова пространства, или, эквивалентно, как множество всех выпуклых комбинаций точек в этом подмножестве. Для ограниченного подмножества плоскости выпуклую оболочку можно представить как фигуру, очерченную резиновой лентой, натянутой вокруг подмножества. Выпуклые оболочки открытых множеств открыты, а выпуклые оболочки компактных множеств компактны. Любое компактное выпуклое множество является выпуклой оболочкой его крайних точек. Оператор выпуклой оболочки является примером оператора замыкания, и любой антиматроид может быть представлен путем применения этого оператора замыкания к конечным наборам точек. Алгоритмические задачи нахождения выпуклой оболочки конечного множества точек на плоскости или в других низкоразмерных евклидовых пространствах, а также двойственная задача о пересечении полупространств, являются фундаментальными задачами вычислительной геометрии. Они могут быть решены за время для двух- или трехмерных наборов точек и за время, соответствующее сложности вывода в наихудшем случае, заданной теоремой о верхней границе в более высоких размерностях. Помимо конечных наборов точек, выпуклые оболочки изучались для простых многоугольников, броуновского движения, пространственных кривых и эпиграфов функций. Выпуклые оболочки широко применяются в математике, статистике, комбинаторной оптимизации, экономике, геометрическом моделировании и этологии. Связанные структуры включают ортогональную выпуклую оболочку, выпуклые слои, триангуляцию Делоне и диаграмму Вороного, а также выпуклый череп.

Равный сходство определений

Не очевидно, что первое определение имеет смысл: почему должно существовать единственное минимальное выпуклое множество, содержащее , для каждого ? Однако второе определение, пересечение всех выпуклых множеств, содержащих , корректно определено. Оно является подмножеством любого другого выпуклого множества, содержащего , поскольку входит в число пересекаемых множеств. Таким образом, это и есть единственное минимальное выпуклое множество, содержащее . Следовательно, первые два определения эквивалентны. Каждое выпуклое множество, содержащее , должно (по предположению о его выпуклости) содержать все выпуклые комбинации точек из , поэтому множество всех выпуклых комбинаций содержится в пересечении всех выпуклых множеств, содержащих . И наоборот, множество всех выпуклых комбинаций само является выпуклым множеством, содержащим , поэтому оно также содержит пересечение всех выпуклых множеств, содержащих , и, следовательно, второе и третье определения эквивалентны. Фактически, согласно теореме Каратеодори, если является подмножеством -мерного евклидова пространства, то любая выпуклая комбинация конечного числа точек из также является выпуклой комбинацией не более точек в . Множество выпуклых комбинаций -кортежа точек является симплексом; на плоскости это треугольник, а в трехмерном пространстве – тетраэдр. Поэтому любая выпуклая комбинация точек из принадлежит симплексу, вершины которого принадлежат , и третье и четвертое определения эквивалентны.

Закрытые и открытые корпуса

Закрытый выпуклый корпус множества — это замыкание выпуклого корпуса, а открытый выпуклый корпус — это внутренность (или в некоторых источниках относительная внутренность) выпуклого корпуса. Закрытый выпуклый корпус множества S — это пересечение всех замкнутых полупространств, содержащих S. Если выпуклый корпус множества S уже является замкнутым множеством (как это происходит, например, если S — конечное множество или, в более общем случае, компактное множество), то он равен закрытому выпуклому корпусу. Однако пересечение замкнутых полупространств само по себе замкнуто, поэтому, когда выпуклый корпус не замкнут, его нельзя представить таким образом. Если открытый выпуклый корпус множества S является n-мерным, то каждая точка корпуса принадлежит открытому выпуклому корпусу, образованному не более чем n точками из S. Множества вершин квадрата, правильного октаэдра или более высокомерного кросс-политопа служат примерами, где требуется ровно n точек.

Сохранение топологических свойств

Топологически, выпуклый корпус открытого множества всегда сам открыт, а выпуклый корпус компактного множества всегда сам компактен. Однако существуют замкнутые множества, для которых выпуклый корпус не является замкнутым. Например, замкнутое множество (множество точек, лежащих на или выше ведьмы Агнези) имеет открытую верхнюю полуплоскость в качестве своего выпуклого корпуса. Компактность выпуклых корпусов компактных множеств в конечномерных евклидовых пространствах обобщается теоремой Крейна — Смуляна, согласно которой замкнутый выпуклый корпус слабо компактного подмножества банахова пространства (подмножества, компактного в слабой топологии) является слабо компактным.

Крайние точки

Крайняя точка выпуклого множества — это точка в этом множестве, которая не лежит на открытом отрезке, соединяющем любые две другие точки того же множества. Для выпуклой оболочки каждая крайняя точка должна быть частью исходного множества, иначе её нельзя представить как выпуклую комбинацию исходных точек. Согласно теореме Крейна — Мильмана, любое компактное выпуклое множество в евклидовом пространстве (или, в более общем случае, в локально выпуклом топологическом векторном пространстве) является выпуклой оболочкой своих крайних точек. Однако это не обязательно верно для выпуклых множеств, которые не являются компактными; например, вся евклидова плоскость и открытый единичный шар являются выпуклыми, но ни у одного из них нет крайних точек. Теория Шоке распространяет эту теорию с конечных выпуклых комбинаций крайних точек на бесконечные комбинации (интегралы) в более общих пространствах.

Сумма Минковского

Операции построения выпуклой оболочки и вычисления суммы Минковского коммутируют друг с другом, в том смысле, что сумма Минковского выпуклых оболочек множеств дает тот же результат, что и выпуклая оболочка суммы Минковского этих же множеств. Это является шагом к теореме Шапли — Фолкмана, ограничивающей расстояние суммы Минковского от её выпуклой оболочки.

Проективная двойственность

Проективная двойственная операция к построению выпуклой оболочки множества точек — это построение пересечения семейства замкнутых полупространств, все из которых содержат начало координат (или любую другую выделенную точку).

Набор конечных точек

Выпуклый корпус конечного множества точек образует выпуклый многоугольник в случае , или, в более общем случае, выпуклый политоп в . Каждая крайняя точка корпуса называется вершиной, и (по теореме Крейна-Милмана) любой выпуклый политоп является выпуклым корпусом своих вершин. Это единственный выпуклый политоп, вершины которого принадлежат и который содержит все точки из . Для множеств точек в общем положении выпуклый корпус является симплициальным политопом. Согласно теореме об верхней границе, число граней выпуклого корпуса точек в -мерном евклидовом пространстве равно . В частности, в двух и трех измерениях число граней не более чем линейно зависит от .

Простые многоугольники

Выпуклый корпус простого многоугольника охватывает данный многоугольник и разделяется им на области, одной из которых является сам многоугольник. Другие области, ограниченные ломаной многоугольника и одним ребром выпуклого корпуса, называются карманами. Рекурсивное вычисление того же разложения для каждого кармана формирует иерархическое описание данного многоугольника, называемое его деревом выпуклых разностей. Отражение кармана относительно ребра выпуклого корпуса расширяет данный простой многоугольник в многоугольник с тем же периметром и большей площадью, и теорема Эрдеша — Надя утверждает, что этот процесс расширения в конечном итоге завершается.

Браунское движение

Кривая, порожденная броуновским движением на плоскости, в любой фиксированный момент времени с вероятностью 1 имеет выпуклую оболочку, граница которой является непрерывно дифференцируемой кривой. Однако для любого угла в диапазоне , найдутся моменты времени во время броуновского движения, когда движущаяся частица касается границы выпуклой оболочки в точке с этим углом. Размерность Хаусдорфа множества этих исключительных моментов времени (с большой вероятностью) равна .

Пространственные кривые

Для выпуклого корпуса пространственной кривой или конечного набора пространственных кривых в общем положении в трехмерном пространстве, части границы, не лежащие на кривых, являются развиваемыми и линейчатыми поверхностями. Примеры включают олоид, выпуклый корпус двух окружностей в перпендикулярных плоскостях, каждая из которых проходит через центр другой, сферикон, выпуклый корпус двух полуокружностей в перпендикулярных плоскостях с общим центром, и D-формы – выпуклые тела, полученные из теоремы единственности Александрова для поверхности, образованной склеиванием двух плоских выпуклых множеств с одинаковым периметром.

Функции

Выпуклый корпус или нижняя выпуклая оболочка функции на вещественном векторном пространстве — это функция, эпиграф которой является нижней выпуклой оболочкой эпиграфа исходной функции. Это единственная максимальная выпуклая функция, мажорирующая исходную функцию. Определение можно расширить на выпуклый корпус множества функций (получаемый из выпуклого корпуса объединения их эпиграфов или, что эквивалентно, из их поточечного минимума), и в этой форме он является двойственным к операции выпуклого сопряжения.

Вычисления

В вычислительной геометрии известно несколько алгоритмов для вычисления выпуклой оболочки для конечного набора точек и для других геометрических объектов. Вычисление выпуклой оболочки означает построение однозначного и эффективного представления требуемой выпуклой формы. Рассматриваемые варианты представления выпуклых оболочек точечных множеств включают список линейных неравенств, описывающих грани оболочки, неориентированный граф граней и их смежности, или полную решетку граней оболочки. В двух измерениях может быть достаточно просто перечислить точки, являющиеся вершинами, в циклическом порядке вокруг оболочки. Для выпуклых оболочек в двух или трех измерениях сложность соответствующих алгоритмов обычно оценивается в терминах , количества входных точек, и , количества точек на выпуклой оболочке, которое может быть значительно меньше, чем . Для оболочек более высокой размерности количество граней других размерностей также может учитываться при анализе. Алгоритм сканирования Грэма может вычислить выпуклую оболочку точек на плоскости за время . Для точек в двух и трех измерениях известны более сложные алгоритмы, чувствительные к объему выходных данных, которые вычисляют выпуклую оболочку за время . К ним относятся алгоритм Чана и алгоритм Киркпатрика — Сейдела. Для размерностей время вычисления выпуклой оболочки составляет , что соответствует наихудшей сложности выходных данных для этой задачи. Выпуклую оболочку простого многоугольника на плоскости можно построить за линейное время. Динамические структуры данных выпуклой оболочки могут использоваться для отслеживания выпуклой оболочки набора точек при вставке и удалении точек, а кинетические структуры выпуклой оболочки могут отслеживать выпуклую оболочку для непрерывно движущихся точек. Построение выпуклых оболочек также служит инструментом, строительным блоком для ряда других алгоритмов вычислительной геометрии, таких как метод вращающихся калиперов для вычисления ширины и диаметра набора точек.

Приложения

Выпуклые оболочки имеют широкое применение во многих областях. В математике выпуклые оболочки используются для изучения полиномов, собственных значений матриц и унитарных элементов, а несколько теорем в дискретной геометрии оперируют с выпуклыми оболочками. Они применяются в робастной статистике как внешняя граница глубины Тьюки, являются частью визуализации данных в двумерном пространстве и определяют множества рисков рандомизированных правил принятия решений. Выпуклые оболочки индикаторных векторов решений комбинаторных задач играют центральную роль в комбинаторной оптимизации и полиэдрической комбинаторике. В экономике выпуклые оболочки позволяют применять методы выпуклости к невыпуклым рынкам. В геометрическом моделировании свойство выпуклости оболочки кривых Безье помогает находить их точки пересечения, а выпуклые оболочки используются при измерении корпусов судов. И в изучении поведения животных выпуклые оболочки применяются в стандартном определении домашнего ареала.

Математика

Ньютоновские полигоны унивариантных многочленов и Ньютоновские политопы многовариантных многочленов — это выпуклые оболочки точек, полученные из степеней членов многочлена, и могут использоваться для анализа асимптотического поведения многочлена и оценок его корней. Выпуклые оболочки и многочлены также связаны в теореме Гаусса — Лукаса, согласно которой корни производной многочлена лежат внутри выпуклой оболочки корней многочлена. В спектральном анализе числовой диапазон нормальной матрицы является выпуклой оболочкой её собственных значений. Теорема Руссо — Дайе описывает выпуклые оболочки унитарных элементов в C*-алгебре. В дискретной геометрии теорема Радона и теорема Тверберга касаются существования разбиений множеств точек на подмножества с пересекающимися выпуклыми оболочками. Определения выпуклого множества как содержащего отрезки между его точками и выпуклой оболочки как пересечения всех выпуклых надмножеств применимы как к гиперболическим пространствам, так и к евклидовым пространствам. Однако в гиперболическом пространстве также можно рассматривать выпуклые оболочки множеств идеальных точек — точек, не принадлежащих самому гиперболическому пространству, но лежащих на границе модели этого пространства. Границы выпуклых оболочек идеальных точек трёхмерного гиперболического пространства аналогичны развёрнутым поверхностям в евклидовом пространстве, и их метрические свойства играют важную роль в гипотезе геометризации в низкоразмерной топологии. Гиперболические выпуклые оболочки также использовались при вычислении канонических триангуляций гиперболических многообразий и применялись для определения эквивалентности узлов. См. также раздел о броуновском движении для применения выпуклых оболочек к этой теме и раздел о пространственных кривых для их применения к теории развиваемых поверхностей.

Статистика

В робастной статистике выпуклая оболочка является одним из ключевых компонентов бэгплота – метода визуализации рассеяния двумерных точек выборки. Контуры глубины Тьюки формируют вложенное семейство выпуклых множеств, при этом выпуклая оболочка является самым внешним, а бэгплот также отображает другой многоугольник из этого вложенного семейства – контур глубины 50%. В теории статистического принятия решений множество рисков рандомизированного правила принятия решений представляет собой выпуклую оболочку точек риска его базовых детерминированных правил принятия решений.

Комбинаторная оптимизация

В комбинаторной оптимизации и полиэдрической комбинаторике центральными объектами исследования являются выпуклые оболочки индикаторных векторов решений комбинаторной задачи. Если удается найти грани этих политопов, описывая политопы как пересечения полупространств, то алгоритмы, основанные на линейном программировании, могут быть использованы для поиска оптимальных решений. В многокритериальной оптимизации также используется другой тип выпуклой оболочки – выпуклая оболочка векторов весов решений. Можно максимизировать любую квазиконвексную комбинацию весов, находя и проверяя каждую вершину выпуклой оболочки, зачастую более эффективно, чем проверять все возможные решения.

Экономика

В модели общего экономического равновесия Арроу-Дебрё предполагается, что агенты обладают выпуклыми множествами бюджетных ограничений и выпуклыми предпочтениями. Эти предположения о выпуклости в экономике могут быть использованы для доказательства существования равновесия. Если реальные экономические данные не являются выпуклыми, их можно преобразовать в выпуклые, используя выпуклые оболочки. Теорема Шапли-Фолкмана позволяет показать, что для больших рынков такое приближение является точным и приводит к "квазиравновесию" для исходного невыпуклого рынка.

Геометрическое моделирование

В геометрическом моделировании одним из ключевых свойств кривой Безье является то, что она находится внутри выпуклой оболочки своих контрольных точек. Это так называемое "свойство выпуклой оболочки" может быть использовано, например, для быстрого определения пересечений этих кривых. В геометрии проектирования лодок и судов, обхват по ватерлинии – это мера размера парусного судна, определяемая с использованием выпуклой оболочки поперечного сечения корпуса судна. Он отличается от периметра поперечного сечения, за исключением лодок и судов, имеющих выпуклый корпус.

Этология

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

Квантовая физика

В квантовой физике пространство состояний любой квантовой системы — множество всех возможных способов подготовки системы — представляет собой выпуклую оболочку, крайними точками которой являются положительно полуопределённые операторы, известные как чистые состояния, а внутренние точки называются смешанными состояниями. Теорема Шрёдингера — Гей-Джей-Вигнера доказывает, что любое смешанное состояние может быть представлено как выпуклая комбинация чистых состояний множеством различных способов.

Термодинамика

Выпуклая оболочка в термодинамике была выявлена Джозией Виллардом Гиббсом (1873), хотя статья была опубликована до того, как эта область стала называться выпуклой оболочкой. В наборе энергий различных стехиометрий материала стабильными будут только измерения, лежащие на нижней выпуклой оболочке. При удалении точки с оболочки и последующем вычислении расстояния до нее, расстояние до новой оболочки отражает степень стабильности фазы.

История

Нижний выпуклый корпус точек на плоскости впервые появляется в форме ньютоновского многоугольника в письме Исаака Ньютона Генри Олденбургу в 1676 году. Сам термин "выпуклый корпус" встречается уже в трудах , а соответствующий термин на немецком языке появился еще раньше, например, в рецензии Ганса Радемахера. В этот же период использовались и другие термины, такие как "выпуклая оболочка". К 1938 году, согласно Ллойду Дайнсу, термин "выпуклый корпус" стал общепринятым; Дайнс отмечает, что считает этот термин неудачным, поскольку в разговорном языке слово "корпус" обычно подразумевает поверхность фигуры, в то время как выпуклый корпус включает в себя и внутреннюю область, а не только поверхность.