В геометрии, выпуклая оболочка или выпуклая оболочка или выпуклое замыкание формы является наименьшим выпуклым установить, который его содержит. Выпуклая оболочка может быть определена либо как пересечение всех выпуклых множеств, содержащих данное подмножество евклидова пространства, либо, что эквивалентно, как множество всех выпуклых комбинаций точек в подмножестве. Для ограниченного подмножества плоскости выпуклая оболочка может быть визуализирована как форма, заключенная в резиновую ленту, натянутую вокруг подмножества.
Выпуклые оболочки открытых множеств открыты, а выпуклые оболочки компактов компактны. Каждое компактное выпуклое множество является выпуклой оболочкой своих крайних точек. Оператор выпуклой оболочки является примером оператора замыкания , и каждый антиматроид может быть представлен путем применения этого оператора замыкания к конечным наборам точек. алгоритмические проблемы поиска выпуклой оболочки конечного множества точек на плоскости или других низкоразмерных евклидовых пространствах, а также его двойственная проблема пересечения полупространств, являются фундаментальными проблемами вычислительной геометрии. Они могут быть решены за время для двух- или трехмерных наборов точек, и за время, соответствующее худшему случаю. сложность, заданная теоремой о верхней оценке в высших измерениях.
Как и для конечных точечных множеств, выпуклые оболочки также изучались для простых многоугольников, броуновского движения, пространственных кривых и эпиграфы функций. Выпуклые оболочки имеют широкое применение в математике, статистике, комбинаторной оптимизации, экономике, геометрическом моделировании и этологии. Связанные структуры включают ортогональную выпуклую оболочку, выпуклые слои, триангуляцию Делоне и диаграмму Вороного и выпуклый череп.
Набор точек в евклидовом пространстве определяется как выпуклый, если он содержит отрезки прямых, соединяющие каждую пару его точек. Выпуклая оболочка данного набора может быть определена как
Для ограниченных множеств на евклидовой плоскости, а не все на одной прямой, границей выпуклой оболочки является простая замкнутая кривая с минимальным периметром , содержащая . Можно представить себе растягивание резиновой ленты так, чтобы она охватывала весь набор , а затем отпускание ее, позволяя ей сжаться; когда он становится тугим, он охватывает выпуклую оболочку . Эта формулировка не сразу обобщается на более высокие измерения: для конечного набора точек в трехмерном пространстве окрестность остовного дерева точек охватывает их со сколь угодно малой площадью поверхности, меньшей, чем площадь поверхности выпуклой оболочки. Однако в более высоких измерениях варианты проблемы препятствий поиска поверхности с минимальной энергией над заданной формой могут иметь выпуклую оболочку в качестве своего решения.
Для объектов в трех измерениях, Первое определение гласит, что выпуклая оболочка является наименьшим возможным выпуклым ограничивающим объемом объектов. Определение с использованием пересечений выпуклых множеств может быть расширено до неевклидовой геометрии, а определение с использованием выпуклых комбинаций может быть расширено с евклидовых пространств до произвольных вещественных векторных пространств или аффинных пробелы ; Выпуклые оболочки также могут быть обобщены более абстрактно на ориентированные матроиды.
Неочевидно, что первое определение имеет смысл: почему должно существует уникальный минимальный выпуклый набор, содержащий , для каждого ? Однако второе определение, пересечение всех выпуклых множеств, содержащих , четко определено. Это подмножество любого другого выпуклого множества , которое содержит , поскольку входит в число пересекаемых множеств. Таким образом, это в точности единственный минимальный выпуклый набор, содержащий . Следовательно, первые два определения эквивалентны.
Каждый выпуклый набор, содержащий , должен (в предположении, что он выпуклый) содержать все выпуклые комбинации точек в , поэтому набор всех выпуклых комбинаций содержится на пересечении всех выпуклых множеств, содержащих . И наоборот, набор всех выпуклых комбинаций сам по себе является выпуклым множеством, содержащим , поэтому он также содержит пересечение всех выпуклых множеств, содержащих , поэтому второе и третье определения эквивалентны.
Фактически, согласно теореме Каратеодори, если - это подмножество -мерного евклидова пространства, каждая выпуклая комбинация конечного числа точек из также является выпуклой комбинацией максимум точек в . Набор выпуклых комбинаций -набора точек представляет собой симплекс ; в плоскости это треугольник, а в трехмерном пространстве - тетраэдр. Следовательно, каждая выпуклая комбинация точек принадлежит симплексу, вершины которого принадлежат , а третье и четвертое определения эквивалентны.
В двух измерениях выпуклый корпус иногда делится на две части, верхнюю и нижнюю части корпуса, простирающиеся между крайним левым и крайним правым точки корпуса. В более общем смысле, для выпуклой оболочки в любом измерении можно разделить границу корпуса на точки, направленные вверх (точки, для которых восходящий луч не пересекается с корпусом), точки, направленные вниз, и крайние точки. Для трехмерных корпусов обращенные вверх и вниз части границы образуют топологические диски.
Замкнутая выпуклая оболочка набора - это замыкание выпуклой оболочки, а открытая выпуклая оболочка - это внутренность (или в некоторых источниках относительная внутренность ) выпуклой оболочки.
Замкнутая выпуклая оболочка является пересечением всех замкнутых полупространств, содержащих . Если выпуклая оболочка уже является замкнутым множеством (как, например, если является конечным множеством или, в более общем смысле, компактным множеством ), тогда он равен замкнутой выпуклой оболочке. Однако пересечение замкнутых полупространств само замкнуто, поэтому, когда выпуклая оболочка не замкнута, она не может быть представлена таким образом.
Если открытая выпуклая оболочка множества является -мерным, тогда каждая точка корпуса принадлежит открытой выпуклой оболочке размером не более точек из . Наборы вершин квадратного, правильного октаэдра или многомерного кросс-многогранника дают примеры, когда требуется ровно точек.
Топологически выпуклая оболочка открытого множества всегда само открыто, и выпуклая оболочка компакта всегда сама компактна. Однако существуют замкнутые множества, для которых выпуклая оболочка не замкнута. Например, замкнутое множество
(набор точек, которые лежат на ведьме Агнеси или выше) имеет открытую верхнюю полуплоскость в качестве выпуклой оболочки.
Компактность Выпуклые оболочки компактных множеств в конечномерных евклидовых пространствах обобщаются с помощью теоремы Крейна – Смулиана, согласно которой замкнутая выпуклая оболочка слабо компактного подмножества банахова пространства (подмножество, компактное при слабой топологии ) слабо компактно.
An e xtreme point выпуклого множества - это точка в множестве, которая не лежит на отрезке прямой между любыми другими двумя точками того же множества. Для выпуклой оболочки каждая крайняя точка должна быть частью данного множества, потому что в противном случае она не может быть сформирована как выпуклая комбинация данных точек. Согласно теореме Крейна – Мильмана, каждое компактное выпуклое множество в евклидовом пространстве (или, в более общем смысле, в локально выпуклом топологическом векторном пространстве ) является выпуклой оболочкой своих крайних точек. Однако это может быть неверно для некомпактных выпуклых множеств; например, вся евклидова плоскость и открытый единичный шар выпуклы, но ни у одной из них нет крайних точек. Теория Шоке расширяет эту теорию от конечных выпуклых комбинаций крайних точек до бесконечных комбинаций (интегралов) в более общих пространствах.
Оператор выпуклой оболочки имеет характерные свойства оператора замыкания :
При применении к конечному набору пои. nts, это оператор замыкания антиматроида, антиматроида-обстрела набора точек. Таким образом, каждый антиматроид может быть представлен выпуклой оболочкой точек в евклидовом пространстве достаточно высокой размерности.
Операции построения выпуклой оболочки и взятия Суммы Минковского коммутируют друг с другом в том смысле, что сумма Минковского выпуклых оболочек множеств дает тот же результат, что и выпуклая оболочка суммы Минковского тех же множеств. Это является шагом к теореме Шепли – Фолкмана, ограничивающей расстояние суммы Минковского от ее выпуклой оболочки.
Проективная двойственность операция по построению выпуклой оболочки набора точек состоит в построении пересечения семейства замкнутых полупространств, которые все содержат начало координат (или любую другую обозначенную точку).
Выпуклая оболочка конечного множества точек образует выпуклый многоугольник, когда , или, в более общем смысле, выпуклый многогранник в . Каждая крайняя точка оболочки называется вершиной, и (по теореме Крейна – Мильмана) каждый выпуклый многогранник является выпуклой оболочкой своих вершин. Это уникальный выпуклый многогранник, вершины которого принадлежат и который охватывает все . Для множеств точек в общего положения выпуклая оболочка является симплициальным многогранником.
Согласно теореме о верхней оценке, количество граней выпуклой оболочки точек в -мерном евклидовом пространстве . В частности, в двух и трех измерениях число граней не более чем линейно в .
Выпуклая оболочка простой многоугольник охватывает данный многоугольник и разделяется им на области, одна из которых является самим многоугольником. Остальные области, ограниченные многоугольной цепочкой многоугольника и одним выпуклым краем корпуса, называются карманами. Рекурсивное вычисление одного и того же разложения для каждого кармана формирует иерархическое описание данного многоугольника, называемое его выпуклым деревом разностей. Отражение кармана через его выпуклый край корпуса расширяет данный простой многоугольник в многоугольник с тем же периметром и большей площадью, и теорема Эрдеша – Надя утверждает, что этот процесс расширения в конечном итоге прекращается.
Кривая, порожденная броуновским движением на плоскости в любой фиксированный момент времени, имеет вероятность 1 иметь выпуклую оболочку, граница которой образует непрерывно дифференцируемую кривую. Однако для любого угла в диапазоне во время броуновского движения будут моменты, когда движущаяся частица касается граница выпуклой оболочки под углом . размерность Хаусдорфа этого набора исключительных времен составляет (с большой вероятностью) .
Для выпуклой оболочки пространственной кривой или конечного набора пространственных кривых в общем положении в трехмерном пространстве, части границы, удаленные от кривых, представляют собой развертывающиеся и линейчатые поверхности. Примеры включают в себя олоид, выпуклую оболочку двух окружностей в перпендикулярных плоскостях, каждая из которых проходит через центр другого, сферикон, выпуклую оболочку двух полукругов в перпендикулярных плоскостях с общим центром., и D-формы - выпуклые формы, полученные из теоремы единственности Александрова для поверхности, образованной склеиванием двух плоских выпуклых множеств с одинаковым периметром.
Выпуклые оболочка или нижняя выпуклая оболочка функции в реальном векторном пространстве - это функция, эпиграф которой является нижней выпуклой оболочкой эпиграфа . Это единственная максимальная выпуклая функция, мажорируемая . Определение может быть расширено до выпуклой оболочки набора функций (полученной из выпуклой оболочки объединения их надграфов или, что то же самое, из их поточечного минимума), и в этой форме оно двойственно выпуклому сопряженному 261>.
В вычислительной геометрии известен ряд алгоритмов для вычисления выпуклой оболочки для конечного набора точек и для других геометрических объектов. Вычисление выпуклой оболочки означает построение однозначного эффективного представления требуемой выпуклой формы. Представления выходных данных, которые были рассмотрены для выпуклой оболочки точечных множеств, включают список линейных неравенств, описывающих фасеты оболочки, неориентированный граф фасетов и их смежности, или полная лицевая решетка корпуса. В двух измерениях может быть достаточно просто перечислить точки, которые являются вершинами, в их циклическом порядке вокруг корпуса.
Для выпуклых корпусов в двух или трех измерениях сложность соответствующих алгоритмов обычно оценивается в члены , количество точек ввода, и , количество точек на выпуклой оболочке, который может быть значительно меньше . Для корпусов больших размеров количество граней других размеров также может входить в анализ. сканирование Грэма может вычислить выпуклую оболочку точек на плоскости во времени . Для точек в двух и трех измерениях известны более сложные чувствительные к выходу алгоритмы, которые вычисляют выпуклую оболочку за время . К ним относятся алгоритм Чана и алгоритм Киркпатрика – Зейделя. Для размеров , время вычисления выпуклой оболочки равно , что соответствует наихудшей выходной сложности задачи. Выпуклая оболочка простого многоугольника на плоскости может быть построена за линейное время.
Динамическая выпуклая оболочка данные структуры могут использоваться для отслеживания выпуклой оболочки набора точек, подвергающихся вставкам и удалению точек, а кинетическая выпуклая оболочка структуры могут отслеживать выпуклую оболочку для точек, движущихся непрерывно. корпуса также служат инструментом, строительным блоком для ряда других вычислительно-геометрических алгоритмов, таких как метод вращающихся штангенциркулей для вычисления ширины и диаметра набор точек.
Некоторые другие формы могут быть определены из набора точек аналогично выпуклой оболочке, как минимальное надмножество с некоторым свойством, пересечение всех форм, содержащих точки из заданного семейства фигур или объединение всех комбинаций точек для определенного типа комбинации. Например:
Триангуляция Делоне точечного множества и его двойственная, Диаграмма Вороного, математически связаны с выпуклой оболочкой: можно просмотреть триангуляцию Делоне точки, установленной в как проекцию выпуклой оболочки в альфа-формы конечного набора точек образуют вложенное семейство (невыпуклых) геометрических объектов, описывающих форма точки, заданная на разных уровнях детализации. Каждая альфа-форма представляет собой объединение некоторых характеристик триангуляции Делоне, выбранных путем сравнения их описанного радиуса с параметром альфа. Сам набор точек образует одну конечную точку этого семейства форм, а его выпуклая оболочка образует другую конечную точку. Выпуклые слои набора точек - это вложенное семейство выпуклых многоугольников, самым внешним из которых является выпуклая оболочка, а внутренние слои построены рекурсивно из точек, не являющихся вершинами выпуклой оболочки.
выпуклый череп многоугольника - это самый большой выпуклый многоугольник, содержащийся внутри него. Его можно найти в полиномиальном времени, но показатель степени алгоритма высокий.
Выпуклые оболочки имеют широкое применение во многих областях. В математике выпуклые оболочки используются для изучения полиномов, матричных собственных значений и унитарных элементов, а несколько теорем в дискретной геометрии включают выпуклые корпуса. Они используются в надежной статистике в качестве внешнего контура глубины Тьюки, являются частью диаграммы визуализации двумерных данных и определяют наборы рисков рандомизированные правила принятия решений. Выпуклые оболочки индикаторных векторов решений комбинаторных задач являются центральными для комбинаторной оптимизации и многогранной комбинаторики. В экономике выпуклые оболочки могут использоваться для применения методов выпуклости в экономике к невыпуклым рынкам. В геометрическом моделировании свойство выпуклого корпуса кривые Безье помогает находить их пересечения, а выпуклые корпуса являются частью измерения корпусов лодок. А при изучении поведения животных выпуклые оболочки используются в стандартном определении домашнего диапазона.
многоугольники Ньютона одномерных многочленов и многогранники Ньютона многомерных многочленов - это выпуклые оболочки точек, полученные из показателей степени членов в многочлен, и может использоваться для анализа асимптотического поведения многочлена и оценок его корней. Выпуклые оболочки и многочлены также объединяются в теореме Гаусса – Лукаса, согласно которой все корни производной многочлена лежат внутри выпуклой оболочки корней многочлена.
В спектральном анализе числовой диапазон нормальной матрицы представляет собой выпуклую оболочку ее собственных значений. Теорема Руссо – Дая описывает выпуклые оболочки унитарных элементов в C * -алгебре. В дискретной геометрии и теорема Радона, и теорема Тверберга касаются существования разбиения точечных множеств на подмножества с пересекающимися выпуклыми оболочками.
определения выпуклого множества как содержащего отрезки прямых между его точками и выпуклой оболочки как пересечения всех выпуклых надмножеств, применяются к гиперболическим пространствам, а также к евклидовым пространствам. Однако в гиперболическом пространстве также можно рассматривать выпуклые оболочки множеств идеальных точек, точек, которые не принадлежат самому гиперболическому пространству, но лежат на границе модели этого пространства. Границы выпуклых оболочек идеальных точек трехмерного гиперболического пространства аналогичны линейчатым поверхностям в евклидовом пространстве, и их метрические свойства играют важную роль в гипотезе геометризации в низкоразмерная топология. Гиперболические выпуклые оболочки также использовались как часть расчета канонических триангуляций гиперболических многообразий и применялись для определения эквивалентности узлов.
См. Также раздел Броуновское движение для применения выпуклых оболочек к этой теме и раздел пространственных кривых для их применения к теории развертывающихся поверхностей.
В устойчивой статистике выпуклая оболочка представляет собой один из ключевых компонентов волынок., способ визуализации распространения двумерных точек выборки. Контуры глубины Тьюки образуют вложенное семейство выпуклых множеств с самой внешней выпуклой оболочкой, и на багплощадке также отображается другой многоугольник из этого вложенного семейства, контур с глубиной 50%.
В статистической теории принятия решений набор рисков рандомизированного правила принятия решений представляет собой выпуклую оболочку точек риска лежащих в его основе детерминированных правил принятия решений.
В комбинаторной оптимизации и многогранной комбинаторике центральными объектами исследования являются выпуклые оболочки индикаторных векторов решений комбинаторной задачи. Если грани этих многогранников могут быть найдены, описывая многогранники как пересечения полупространств, то алгоритмы, основанные на линейном программировании, могут быть использованы для поиска оптимальных решений. В многоцелевой оптимизации также используется другой тип выпуклой оболочки, выпуклая оболочка весовых векторов решений. Любую квазивыпуклую комбинацию весов можно максимизировать, находя и проверяя каждую вершину выпуклой оболочки, что часто более эффективно, чем проверка всех возможных решений.
В Модель Эрроу – Дебре для общего экономического равновесия, предполагается, что агенты имеют выпуклые наборы бюджета и выпуклые предпочтения. Эти предположения о выпуклости в экономике могут использоваться для доказательства существования равновесия. Когда фактические экономические данные невыпуклые, их можно сделать выпуклыми, взяв выпуклые оболочки. Теорема Шепли – Фолкмана может использоваться, чтобы показать, что для крупных рынков это приближение является точным и приводит к «квазиравновесию» для исходного невыпуклого рынка.
В геометрическом моделировании одним из ключевых свойств кривой Безье является то, что она лежит внутри выпуклой оболочки своих контрольных точек. Это так называемое «свойство выпуклости корпуса» можно использовать, например, для быстрого обнаружения пересечений этих кривых.
В геометрии конструкции лодки и корабля обхват цепи является измерением размера парусного судна, определяемого с использованием выпуклой формы корпуса поперечного сечения корпуса судна. Он отличается от обхвата кожи, самого периметра поперечного сечения, за исключением лодок и кораблей, имеющих выпуклый корпус.
Выпуклый корпус является широко известный как минимальный выпуклый многоугольник в этологии, исследовании поведения животных, где это классический, хотя, возможно, упрощенный подход к оценке домашнего диапазона животного на основе точек, где Выбросы могут сделать минимальный выпуклый многоугольник чрезмерно большим, что мотивировало расслабленные подходы, которые содержат только подмножество наблюдений, например, путем выбора одного из выпуклых слоев, который находится близко к цели процента выборок, или в методе локальной выпуклой оболочки путем объединения выпуклых оболочек окрестностей точек.
В квантовой физики, пространство состояний любой квантовой системы - набор всех способов, которыми система может быть подготовлена - представляет собой выпуклую оболочку, крайняя точка ints - это положительно-полуопределенные операторы, известные как чистые состояния, внутренние точки которых называются смешанными состояниями. Теорема Шредингера – HJW доказывает, что любое смешанное состояние может быть записано как выпуклая комбинация чистых состояний множеством способов.
Выпуклая нижняя оболочка точки на плоскости появляются в форме многоугольника Ньютона в письме от Исаака Ньютона к Генри Ольденбургу в 1676 году. Сам термин «выпуклая оболочка» появляется еще в работы Гарретта Биркгофа (1935), и соответствующий термин в немецком появляется раньше, например, в обзоре Ганса Радемахера на Кениг (1922). Другие термины, такие как «выпуклый конверт», также использовались в этот период времени. К 1938 году, согласно Ллойду Дайнсу, термин «выпуклый корпус» стал стандартом; Dines adds that he finds the term unfortunate, because the colloquial meaning of the word "hull" would suggest that it refers to the surface of a shape, whereas the convex hull includes the interior and not just the surface.
The Wikibook Algorithm Implementation has a page on the topic of: Convex hull |