Выпуклая оболочка

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

Выпуклая оболочка красного множества — это выпуклое синее и красное множество .

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

Выпуклые оболочки открытых множеств открыты, а выпуклые оболочки компактов компактны. Всякий выпуклый компакт есть выпуклая оболочка его крайних точек . Оператор выпуклой оболочки является примером оператора замыкания , и каждый антиматроид может быть представлен путем применения этого оператора замыкания к конечному набору точек. Алгоритмические двойственная проблемы поиска выпуклой оболочки конечного набора точек на плоскости или других евклидовых пространствах малой размерности и проблема пересечения полупространств являются фундаментальными проблемами вычислительной геометрии . Их можно решить со временем $O(n\log n)$ для двух- или трехмерных наборов точек и по времени, согласующемуся со сложностью вывода в наихудшем случае, заданной теоремой о верхней границе в более высоких измерениях.

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

Определения

Выпуклая оболочка ограниченного плоского множества: аналогия с резиновой лентой

Множество точек евклидова пространства называется выпуклым, если оно содержит отрезки, соединяющие каждую пару его точек. Выпуклая оболочка данного множества $X$ может быть определен как

1. (Уникальное) минимальное выпуклое множество, содержащее $X$
2. Пересечение всех выпуклых множеств, содержащих $X$
3. Множество всех выпуклых комбинаций точек в $X$
4. Объединение всех симплексов с вершинами в $X$

Для ограниченных множеств на евклидовой плоскости, не всех на одной прямой, граница выпуклой оболочки представляет собой простую замкнутую кривую с минимальным периметром , содержащую $X$. Можно представить, как растягивают резинку так, чтобы она охватывала весь набор. $S$а затем отпуская его, позволяя ему сжаться; когда он становится тугим, он охватывает выпуклую оболочку $S$. Эта формулировка не распространяется сразу на более высокие измерения: для конечного набора точек в трехмерном пространстве окрестность остовного дерева точек окружает их с сколь угодно малой площадью поверхности, меньшей, чем площадь поверхности выпуклой оболочки. Однако в более высоких измерениях варианты проблемы с препятствиями по поиску поверхности с минимальной энергией выше заданной формы могут иметь выпуклую оболочку в качестве решения.

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

Эквивалентность определений

3D-выпуклая оболочка облака из 120 точек

Неочевидно, что первое определение имеет смысл: почему должно существовать единственное минимальное выпуклое множество, содержащее $X$, для каждого $X$? Однако второе определение — пересечение всех выпуклых множеств, содержащих $X$, четко определен. Это подмножество любого другого выпуклого множества. $Y$ который содержит $X$, потому что $Y$входит в число пересекающихся множеств. Таким образом, это в точности единственное минимальное выпуклое множество, содержащее $X$. Следовательно, первые два определения эквивалентны.

Каждое выпуклое множество, содержащее $X$ должен (в предположении, что он выпуклый) содержать все выпуклые комбинации точек из $X$, поэтому множество всех выпуклых комбинаций содержится в пересечении всех выпуклых множеств, содержащих $X$. И наоборот, множество всех выпуклых комбинаций само по себе является выпуклым множеством, содержащим $X$, поэтому оно также содержит пересечение всех выпуклых множеств, содержащих $X$, поэтому второе и третье определения эквивалентны.

Действительно, согласно теореме Каратеодори , если $X$ является подмножеством $d$-мерное евклидово пространство, каждая выпуклая комбинация конечного числа точек из $X$ также является выпуклой комбинацией не более чем $d+1$ указывает на $X$. Множество выпуклых комбинаций $(d+1)$-кортеж точек является симплексом ; на плоскости это треугольник , а в трёхмерном пространстве — тетраэдр. Следовательно, каждая выпуклая комбинация точек $X$ принадлежит симплексу, вершины которого принадлежат $X$, а третье и четвертое определения эквивалентны.

Верхний и нижний корпуса

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

Топологические свойства

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

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

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

Если открытая выпуклая оболочка множества $X$ является $d$-мерной, то каждая точка оболочки принадлежит открытой выпуклой оболочке не более $2d$ точки $X$. Наборы вершин квадрата, правильного октаэдра или многогранника более высокой размерности служат примерами, когда именно $2d$ нужны баллы.

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

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

Топологически выпуклая оболочка открытого множества сама по себе всегда открыта, а выпуклая оболочка компактного множества всегда сама компактна. Однако существуют замкнутые множества, у которых выпуклая оболочка не замкнута. Например, закрытое множество

$\left\{(x,y)\mathop {\bigg |} y\geq {\frac {1}{1+x^{2}}}\right\}$

(набор точек, лежащих на ведьме Аньези или над ней ) имеет открытую верхнюю полуплоскость в качестве выпуклой оболочки.

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

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

Основная статья: теорема Крейна – Милмана

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

Геометрические и алгебраические свойства

Оператор закрытия

Оператор выпуклой оболочки обладает характерными свойствами оператора замыкания :

• Оно обширно , а это означает, что выпуклая оболочка каждого множества $X$ представляет собой надмножество $X$.
• Оно не убывает , то есть для каждых двух наборов $X$ и $Y$ с $X\subseteq Y$, выпуклая оболочка $X$ является подмножеством выпуклой оболочки $Y$.
• Оно идемпотентно , то есть для каждого $X$, выпуклая оболочка выпуклой оболочки $X$ то же самое, что и выпуклая оболочка $X$.

Применительно к конечному набору точек это оператор замыкания антиматроида , обстреливающий антиматроид множества точек. Таким образом, каждый антиматроид может быть представлен выпуклыми оболочками точек в евклидовом пространстве достаточно высокой размерности.

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

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

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

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

Особые случаи

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

Выпуклая оболочка точек на плоскости

Основная статья: Выпуклый многогранник

Выпуклая оболочка конечного множества точек $S\subset \mathbb {R} ^{d}$ образует выпуклый многоугольник , если $d=2$, или, в более общем смысле, выпуклый многогранник в $\mathbb {R} ^{d}$. Каждая крайняя точка оболочки называется вершиной и (по теореме Крейна-Милмана) каждый выпуклый многогранник является выпуклой оболочкой своих вершин. Это единственный выпуклый многогранник, вершины которого принадлежат $S$ и это включает в себя все $S$. Для множеств точек общего положения выпуклая оболочка является симплициальным многогранником .

Согласно теореме о верхней оценке , число граней выпуклой оболочки $n$ указывает на $d$-мерное евклидово пространство – это $O(n^{\lfloor d/2\rfloor })$. В частности, в двух и трех измерениях количество граней не более чем линейно. $n$.

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

Основная статья: Выпуклая оболочка простого многоугольника

Выпуклая оболочка (синий и желтый цвет) простого многоугольника (синий цвет)

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

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

Кривая, порожденная броуновским движением на плоскости, в любой фиксированный момент времени имеет вероятность 1 иметь выпуклую оболочку, граница которой образует непрерывно дифференцируемую кривую . Однако для любого угла $\theta$ В диапазоне $\pi /2<\theta <\pi$, во время броуновского движения будут моменты, когда движущаяся частица касается границы выпуклой оболочки в точке угла $\theta$. Хаусдорфова размерность этого набора исключительных моментов равна (с высокой вероятностью) $1-\pi /2\theta$.

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

Олоид . , выпуклая оболочка двух кругов в трехмерном пространстве

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

Функции

Основная статья: Нижний выпуклый конверт

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

Вычисление

Основная статья: Алгоритмы выпуклой оболочки

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

Для выпуклых двух- и трехмерных оболочек сложность соответствующих алгоритмов обычно оценивается через $n$, количество входных точек и $h$, количество точек на выпуклой оболочке, которое может быть существенно меньше, чем $n$. Для корпусов более высоких размерностей в анализ также может включаться количество граней других измерений. Сканирование Грэма позволяет вычислить выпуклую оболочку $n$ точки на плоскости во времени $O(n\log n)$. Для точек в двух и трех измерениях более сложные алгоритмы, чувствительные к выходным данным , которые вычисляют выпуклую оболочку во времени. известны $O(n\log h)$. К ним относятся алгоритм Чана и алгоритм Киркпатрика-Зейделя . По размерам $d>3$, время вычисления выпуклой оболочки равно $O(n^{\lfloor d/2\rfloor })$, что соответствует выходной сложности задачи в худшем случае. Выпуклая оболочка простого многоугольника на плоскости может быть построена за линейное время .

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

Связанные структуры

Ортогональная выпуклая оболочка

Относительная выпуклая оболочка

Несколько других фигур могут быть определены из набора точек аналогично выпуклой оболочке, как минимальное надмножество с некоторым свойством, пересечение всех фигур, содержащих точки из данного семейства фигур, или объединение всех комбинаций фигур. очков за определенный тип комбинации. Например:

• Аффинная оболочка — это наименьшее аффинное подпространство евклидова пространства, содержащее заданное множество или объединение всех аффинных комбинаций точек в множестве.
• Линейная оболочка — это наименьшее линейное подпространство векторного пространства, содержащее заданный набор, или объединение всех линейных комбинаций точек в наборе.
• Коническая оболочка или положительная оболочка подмножества векторного пространства — это набор всех положительных комбинаций точек в подмножестве.
• Визуальная оболочка трехмерного объекта по отношению к набору точек зрения состоит из точек $p$ так что каждый луч с точки зрения через $p$пересекает объект. Эквивалентно, это пересечение (невыпуклых) конусов, образуемых контуром объекта относительно каждой точки обзора. Он используется в 3D-реконструкции как самая большая форма, которая может иметь одинаковые очертания с заданных точек зрения.
• Круглая оболочка или альфа-оболочка подмножества плоскости - это пересечение всех дисков заданного радиуса. $1/\alpha$ которые содержат подмножество.
• Относительная выпуклая оболочка подмножества двумерного простого многоугольника - это пересечение всех относительно выпуклых надмножеств, где множество внутри одного и того же многоугольника является относительно выпуклым, если оно содержит геодезическую между любыми двумя своими точками.
• Ортогональная выпуклая оболочка или прямолинейная выпуклая оболочка - это пересечение всех ортогонально выпуклых и связных надмножеств, где множество является ортогонально выпуклым, если оно содержит все отрезки, параллельные осям между парами его точек.
• Ортогональная выпуклая оболочка — это частный случай гораздо более общей конструкции, гипервыпуклой оболочки , которую можно рассматривать как наименьшее инъективное метрическое пространство , содержащее точки данного метрического пространства .
• Голоморфно выпуклая оболочка — это обобщение аналогичных понятий на комплексные аналитические многообразия , полученные в результате пересечения множеств подуровней голоморфных функций, содержащих заданное множество.

Триангуляция Делоне множества точек и двойственная ей диаграмма Вороного математически связаны с выпуклыми оболочками: триангуляция Делоне множества точек в $\mathbb {R} ^{n}$ можно рассматривать как проекцию выпуклой оболочки в $\mathbb {R} ^{n+1}.$Альфа -формы конечного набора точек представляют собой вложенное семейство (невыпуклых) геометрических объектов, описывающих форму набора точек на разных уровнях детализации. Каждая форма альфа представляет собой объединение некоторых особенностей триангуляции Делоне, выбранных путем сравнения их радиуса описанной окружности с параметром альфа. Набор точек сам по себе образует одну конечную точку этого семейства фигур, а его выпуклая оболочка образует другую конечную точку. Выпуклые слои набора точек представляют собой вложенное семейство выпуклых многоугольников, самым внешним из которых является выпуклая оболочка, а внутренние слои создаются рекурсивно из точек, которые не являются вершинами выпуклой оболочки.

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

Приложения

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

Математика

Разделение семи точек на три подмножества с пересекающимися выпуклыми оболочками, существование которых гарантировано для любых семи точек плоскости по теореме Тверберга.

Многоугольники Ньютона одномерных многочленов и многогранники Ньютона многомерных многомерных многочленов представляют собой выпуклые оболочки точек, полученные из показателей степеней полинома, и могут использоваться для анализа асимптотического поведения многочлена и оценок его корней. Выпуклые оболочки и многочлены также объединяются в теореме Гаусса-Люкаса , согласно которой все корни производной многочлена лежат внутри выпуклой оболочки корней многочлена.

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

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

См. также раздел о броуновском движении для применения выпуклых оболочек к этому предмету и раздел о пространственных кривых для их применения к теории развертывающихся поверхностей .

Статистика

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

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

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

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

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

Экономика

Основная статья: Выпуклость в экономике

В Эрроу-Дебре модели общего экономического равновесия предполагается, что агенты имеют выпуклые бюджетные множества и выпуклые предпочтения . Эти предположения о выпуклости в экономике можно использовать для доказательства существования равновесия. Когда фактические экономические данные невыпуклые , их можно сделать выпуклыми, взяв выпуклые оболочки. Теорему Шепли -Фолкмана можно использовать, чтобы показать, что для крупных рынков это приближение является точным и приводит к «квазиравновесию» для исходного невыпуклого рынка.

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

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

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

Этология

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

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

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

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

Выпуклая оболочка соединений магния и углерода . Mg ₂ C _{3 будет нестабильным, поскольку он находится над нижней частью корпуса.} Ожидается, что

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

История

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

Ссылки

• Фан, Кай (1959), Выпуклые множества и их приложения. Летние лекции 1959 г. , Аргонская национальная лаборатория.
• Эндрю, AM (1979), «Еще один эффективный алгоритм для выпуклых оболочек в двух измерениях», Information Processing Letters , 9 (5): 216–219, doi : 10.1016/0020-0190(79)90072-3
• Артин, Эмиль (1967), «2.5. Многоугольник Ньютона» , Алгебраические числа и алгебраические функции , Гордон и Брич, стр. 37–43, MR   0237460
• Ауэль, Ашер (2019), «Математика Грейс Мюррей Хоппер» (PDF) , Уведомления Американского математического общества , 66 (3): 330–340, doi : 10.1090/noti1810 , MR   3889348 , S2CID   76650751
• Авис, Дэвид ; Бремнер, Дэвид; Зайдель, Раймунд (1997), «Насколько хороши алгоритмы выпуклой оболочки?», Вычислительная геометрия , 7 (5–6): 265–301, doi : 10.1016/S0925-7721(96)00023-5 , MR   1447243
• Барань, Имре ; Качальский, Меир; Пах, Янош (1982), «Количественные теоремы типа Хелли», Труды Американского математического общества , 86 (1): 109–114, doi : 10.1090/S0002-9939-1982-0663877-X , JSTOR   2044407 , MR   0663877
• Баш, Жюльен; Гибас, Леонидас Дж .; Хершбергер, Джон (1999), «Структуры данных для мобильных данных», Journal of Algorithms , 31 (1): 1–28, CiteSeerX   10.1.1.134.6921 , doi : 10.1006/jagm.1998.0988 , MR   1670903 , S2CID   8013433
• Биркгоф, Гарретт (1935), «Интегрирование функций со значениями в банаховом пространстве», Труды Американского математического общества , 38 (2): 357–378, doi : 10.2307/1989687 , JSTOR   1989687 , MR   1501815
• Браун, KQ (1979), «Диаграммы Вороного из выпуклых оболочек», Information Processing Letters , 9 (5): 223–228, doi : 10.1016/0020-0190(79)90074-7 , S2CID   44537056
• де Берг, М .; ван Кревелд, М .; Овермарс, Марк ; Шварцкопф, О. (2008), Вычислительная геометрия: алгоритмы и приложения (3-е изд.), Springer
• Чан, Тимоти М. (2012), «Три проблемы о динамических выпуклых оболочках», Международный журнал вычислительной геометрии и приложений , 22 (4): 341–364, doi : 10.1142/S0218195912600096 , MR   2994585
• Чанг, Дж. С.; Яп, К.-К. (1986), «Полиномиальное решение задачи чистки картофеля», Дискретная и вычислительная геометрия , 1 (2): 155–182, doi : 10.1007/BF02187692 , MR   0834056
• Шазель, Бернар (1985), «О выпуклых слоях плоского множества», IEEE Transactions on Information Theory , 31 (4): 509–517, doi : 10.1109/TIT.1985.1057060 , MR   0798557
• Шазель, Бернар (1993), «Оптимальный алгоритм выпуклой оболочки в любом фиксированном измерении» (PDF) , Discrete & Computational Geometry , 10 (1): 377–409, CiteSeerX   10.1.1.113.8709 , doi : 10.1007/BF02573985 , S2CID   26605267
• Чен, Циньюй; Ван, Гоочжао (март 2003 г.), «Класс кривых Безье», Компьютерное геометрическое проектирование , 20 (1): 29–39, doi : 10.1016/s0167-8396(03)00003-7
• Крэнстон, М.; Сюй, П.; Марч, П. (1989), «Гладкость выпуклой оболочки плоского броуновского движения», Annals of Probability , 17 (1): 144–150, doi : 10.1214/aop/1176991500 , JSTOR   2244202 , MR   0972777
• Демейн, Эрик Д .; Гассенд, Блез; О'Рурк, Джозеф ; Туссен, Годфрид Т. (2008), «Все многоугольники переворачиваются конечно ... верно?», Обзоры по дискретной и вычислительной геометрии , Современная математика, том. 453, Провиденс, Род-Айленд: Американское математическое общество, стр. 231–255, doi : 10.1090/conm/453/08801 , ISBN  978-0-8218-4239-3 , МР   2405683
• Дайнс, LL (1938), «О выпуклости», American Mathematical Monthly , 45 (4): 199–209, doi : 10.2307/2302604 , JSTOR   2302604 , MR   1524247
• Дирнбёк, Ганс; Стачел, Хельмут (1997), «Развитие олоида» (PDF) , Журнал геометрии и графики , 1 (2): 105–118, MR   1622664
• Эдельсбруннер, Герберт ; Киркпатрик, Дэвид Г .; Зайдель, Раймунд (1983), «О форме множества точек на плоскости», IEEE Transactions on Information Theory , 29 (4): 551–559, doi : 10.1109/TIT.1983.1056714
• Эпштейн, администратор баз данных ; Марден, А. (1987), «Выпуклые оболочки в гиперболическом пространстве, теорема Салливана и измеренные складчатые поверхности», в Эпштейне, DBA (редактор), Аналитические и геометрические аспекты гиперболического пространства (Ковентри / Дарем, 1984) , Серия лекций Лондонского математического общества, том. 111, Кембридж: Издательство Кембриджского университета, стр. 113–253, MR   0903852.
• Эскобар, Лаура; Каве, Киумарс (сентябрь 2020 г.), «Выпуклые многогранники, алгебраическая геометрия и комбинаторика» (PDF) , Уведомления Американского математического общества , 67 (8): 1116–1123, doi : 10.1090/noti2137 , S2CID   221659506
• Фульц, Брент (апрель 2020 г.), Фазовые переходы в материалах , Cambridge University Press, стр. 55, номер домена : 10.1017/9781108641449 , ISBN  9781108641449
• Гарднер, Л. Террелл (1984), «Элементарное доказательство теоремы Руссо-Дая», Proceedings of the American Mathematical Society , 90 (1): 171, doi : 10.2307/2044692 , JSTOR   2044692 , MR   0722439 , S2CID   119501393
• Гельфанд, И.М. ; Капранов М.М. ; Зелевинский, А.В. (1994), «6. Многогранники Ньютона и многогранники Чоу», Дискриминанты, результанты и многомерные определители , Математика: теория и приложения, Биркхойзер, стр. 193–213, doi : 10.1007/978-0-8176-4771 -1 , ISBN  0-8176-3660-9 , МР   1264417
• Гетц, Уэйн М.; Уилмерс, Кристофер К. (2004), «Локальная конструкция выпуклой оболочки ближайшего соседа для домашних диапазонов и распределений использования» (PDF) , Ecography , 27 (4), Wiley: 489–505, doi : 10.1111/j.0906 -7590.2004.03835.x , S2CID   14592779
• Гиббс, Уиллард Дж. (1873), «Метод геометрического представления термодинамических свойств веществ с помощью поверхностей», Труды Академии искусств и наук Коннектикута , 2 : 382–404 ; перепечатано в «Научных статьях Дж. Уилларда Гиббса», Vol. I: Термодинамика , Longmans, Green, & Co., 1906, стр. 33–54.
• Грэм, Рональд Л .; Яо, Ф. Фрэнсис (1983), «Нахождение выпуклой оболочки простого многоугольника», Journal of Algorithms , 4 (4): 324–331, doi : 10.1016/0196-6774(83)90013-5 , MR   0729228
• Грюнбаум, Бранко (2003), Выпуклые многогранники , Тексты для выпускников по математике, том. 221 (2-е изд.), Спрингер, ISBN  9780387004242
• Гастин, Уильям (1947), «Внутри выпуклой оболочки евклидова множества», Бюллетень Американского математического общества , 53 (4): 299–301, doi : 10.1090/S0002-9904-1947-08787-5 , МР   0020800
• Харрис, Бернард (1971), «Математические модели для статистической теории принятия решений» (PDF) , Методы оптимизации в статистике (Proc. Sympos., Университет штата Огайо, Колумбус, Огайо, 1971) , стр. 369–389, MR   0356305
• Отье, Жоффруа (2014), «Подходы к интеллектуальному анализу данных для высокопроизводительного прогнозирования кристаллической структуры и соединений», в Атахан-Эвренк, Суле; Аспуру-Гузик, Алан (ред.), Прогнозирование и расчет кристаллических структур: методы и приложения , Темы современной химии, том. 345, Springer International Publishing, стр. 139–179, номер документа : 10.1007/128_2013_486 , ISBN.  978-3-319-05773-6 , ПМИД   24287952 ; см . стр. 143
• Херрлих, Хорст (1992), «Гипервыпуклые оболочки метрических пространств», Труды симпозиума по общей топологии и приложениям (Оксфорд, 1989), Топология и ее приложения , 44 (1–3): 181–187, doi : 10.1016/ 0166-8641(92)90092-Е , МР   1173256
• Джонсон, Чарльз Р. (1976), «Нормальность и числовой диапазон», Линейная алгебра и ее приложения , 15 (1): 89–94, doi : 10.1016/0024-3795(76)90080-x , MR   0460358
• Кашивабара, Кенджи; Накамура, Масатака; Окамото, Ёсио (2005), «Теорема об аффинном представлении абстрактных выпуклых геометрий», Computational Geometry , 30 (2): 129–144, CiteSeerX   10.1.1.14.4965 , doi : 10.1016/j.comgeo.2004.05.001 , MR   2107032
• Като, Наоки (1992), «Проблемы оптимизации сети по двум критериям», Транзакции IEICE по основам электроники, связи и компьютерных наук , E75-A: 321–329
• Кернохан, Брайан Дж.; Гитцен, Роберт А.; Миллспо, Джошуа Дж. (2001), «Анализ использования пространства и перемещений животных», в Миллспо, Джошуа; Марзлафф, Джон М. (ред.), Радиослежение и популяции животных , Academic Press, ISBN  9780080540221
• Ким, Суран; Ким, Кю; Ку, Джахён; Ли, Хункён; Мин, Бён Иль; Ким, Дак Янг (декабрь 2019 г.), «Фазовые переходы, индуцированные давлением, и сверхпроводимость в карбидах магния», Scientific Reports , 9 (1): 20253, Bibcode : 2019NatSR...920253K , doi : 10.1038/s41598-019-56497- 6 , ПМК   6934831 , ПМИД   31882982
• Киркпатрик, К.А. (2006), «Теорема Шредингера-ХЮВ», Foundations of Physics Letters , 19 (1): 95–102, arXiv : quant-ph/0305068 , Bibcode : 2006FoPhL..19...95K , doi : 10.1007/s10702-006-1852-1 , S2CID   15995449
• Кисельман, Кристер О. (2002), «Полугруппа операторов в теории выпуклости», Труды Американского математического общества , 354 (5): 2035–2053, doi : 10.1090/S0002-9947-02-02915-X , MR   1881029
• Кнут, Дональд Э. (1992), Аксиомы и оболочки , Конспекты лекций по информатике, том. 606, Гейдельберг: Springer-Verlag, номер номера : 10.1007/3-540-55611-7 , ISBN.  3-540-55611-7 , MR   1226891 , S2CID   5452191 , заархивировано из оригинала 20 июня 2017 г. , получено 15 сентября 2011 г.
• Кениг, Денес (декабрь 1922 г.), «О выпуклых телах», Mathematical Journal , 14 (1): 208–210, doi : 10.1007/bf01215899 , S2CID   128041360 ; см. также обзор Ганса Радемахера (1922), ЖФМ   48.0835.01
• Крейн, Марк ; Милман, Дэвид (1940), «О крайних точках правильных выпуклых множеств» , Studia Mathematica , 9 : 133–138, doi : 10.4064/sm-9-1-133-138
• Крейн, М .; Шмулян, В. (1940), «О правильно выпуклых множествах в пространстве, сопряженном с банаховым пространством», Annals of Mathematics , Second Series, 41 (3): 556–583, doi : 10.2307/1968735 , hdl : 10338.dmlcz /100106 , JSTOR   1968735 , MR   0002009
• Лаурентини, А. (1994), «Концепция визуальной оболочки для понимания изображений на основе силуэтов», IEEE Transactions on Pattern Analysis and Machine Intelligence , 16 (2): 150–162, doi : 10.1109/34.273735
• Лэй, Стивен Р. (1982), Выпуклые множества и их приложения , John Wiley & Sons, ISBN  0-471-09584-2 , МР   0655598
• Ли, Д.Т. (1983), «О поиске выпуклой оболочки простого многоугольника», Международный журнал компьютерных и информационных наук , 12 (2): 87–98, doi : 10.1007/BF00993195 , MR   0724699 , S2CID   28600832
• Мейсон, Герберт Б. (1908), Энциклопедия кораблей и судоходства , стр. 698
• МакКаллум, Дункан; Авис, Дэвид (1979), «Линейный алгоритм поиска выпуклой оболочки простого многоугольника», Information Processing Letters , 9 (5): 201–206, doi : 10.1016/0020-0190(79)90069-3 , MR   0552534
• Ньютон, Исаак (24 октября 1676 г.), «Письмо Генри Ольденбургу» , Проект Ньютона , Оксфордский университет.
• Никола, Пьеркарло (2000), «Общее конкурентное равновесие», Основная математическая экономика в 20 веке , Springer, стр. 197–215, doi : 10.1007/978-3-662-04238-0_16 , ISBN  978-3-642-08638-0
• Нильсен, Эрленд Б.; Педерсен, Симен; Линнелл, Джон, округ Колумбия (2008), «Можно ли использовать минимальные диапазоны домов выпуклых многоугольников для получения биологически значимых выводов?», Ecoological Research , 23 (3): 635–639, Bibcode : 2008EcoR...23..635N , doi : 10.1007/s11284-007-0421-9 , S2CID   30843551
• Оберман, Адам М. (2007), «Выпуклая оболочка — это решение нелинейной проблемы с препятствиями», Proceedings of the American Mathematical Society , 135 (6): 1689–1694, doi : 10.1090/S0002-9939-07-08887 -9 , МР   2286077
• Окон, Т. (2000), «Теория Шоке в метрических пространствах», Журнал анализа и его приложений , 19 (2): 303–314, doi : 10.4171/ZAA/952 , MR   1768994
• Оттманн, Т.; Сойсалон-Сойнинен, Э.; Вуд, Дерик (1984), «Об определении и вычислении прямолинейных выпуклых оболочек», Information Sciences , 33 (3): 157–171, doi : 10.1016/0020-0255(84)90025-2
• Прасолов, Виктор В. (2004), «1.2.1 Теорема Гаусса – Лукаса» , Полиномы , алгоритмы и вычисления в математике, том. 11, Springer, стр. 12–13, номер документа : 10.1007/978-3-642-03980-5 , ISBN.  3-540-40714-6 , МР   2082772
• Пуллибланк, WR (1983), «Многогранная комбинаторика», в Бачеме, Ахиме; Корте, Бернхард; Гретшель, Мартин (ред.), Математическое программирование: современное состояние (XI-й Международный симпозиум по математическому программированию, Бонн, 1982 г.) , Springer, стр. 312–345, doi : 10.1007/978-3-642-68874-4_13 , ISBN  978-3-642-68876-8
• Раппопорт, Ари (1992), «Эффективный адаптивный алгоритм построения дерева выпуклых разностей простого многоугольника», Computer Graphics Forum , 11 (4): 235–240, doi : 10.1111/1467-8659.1140235 , S2CID   20137707
• Рей, Джон Р. (1979), «Несколько обобщений теоремы Тверберга», Israel Journal of Mathematics , 34 (3): 238–244 (1980), doi : 10.1007/BF02760885 , MR   0570883 , S2CID   121352925
• Риффель, Элеонора Г .; Полак, Вольфганг Х. (2011), Квантовые вычисления: нежное введение , MIT Press, стр. 215–216, ISBN  978-0-262-01506-6
• Рокафеллар, Р. Тиррелл (1970), Выпуклый анализ , Princeton Mathematical Series, vol. 28, Принстон, Нью-Джерси: Издательство Принстонского университета, MR   0274683
• Росси, Хьюго (1961), «Голоморфно выпуклые множества с несколькими комплексными переменными», Annals of Mathematics , Second Series, 74 (3): 470–493, doi : 10.2307/1970292 , JSTOR   1970292 , MR   0133479
• Руссиу, Питер Дж .; Рутс, Ида; Тьюки, Джон В. (1999), «Сюжет мешка: двумерный коробчатый график», The American Statistician , 53 (4): 382–387, doi : 10.1080/00031305.1999.10474494
• Сакума, Ицуо (1977), «Замкнутость выпуклых оболочек», Журнал экономической теории , 14 (1): 223–227, doi : 10.1016/0022-0531(77)90095-3
• Шнайдер, Рольф (1993), Выпуклые тела: теория Брунна-Минковского , Энциклопедия математики и ее приложений, том. 44, Кембридж: Издательство Кембриджского университета, номер домена : 10.1017/CBO9780511526282 (неактивен 18 марта 2024 г.), ISBN  0-521-35220-7 , МР   1216521 {{citation}}: CS1 maint: DOI неактивен по состоянию на март 2024 г. ( ссылка )
• Ситон, Кэтрин А. (2017), «Сфериконы и D-формы: связанная крючком связь», Журнал математики и искусств , 11 (4): 187–202, arXiv : 1603.08409 , doi : 10.1080/17513472.2017.1318512 , MR   3765242 , S2CID   84179479
• Седых, В.Д. (1981), "Строение выпуклой оболочки пространственной кривой", Труды семинара имени И.Г. Петровского (6): 239–256, MR   0630708 , перевод в Журнале советской математики 33 (4): 1140–1153, 1986, дои : 10.1007/BF01086114
• Зонтаг, Эдуардо Д. (1982), «Замечания о кусочно-линейной алгебре» , Pacific Journal of Mathematics , 98 (1): 183–201, doi : 10.2140/pjm.1982.98.183 , MR   0644949 , S2CID   18446330
• Стейниц, Э. (1914), «Условно сходящиеся ряды и выпуклые системы. (Продолжение)», Journal für die Pure und Angewandte Mathematics , 1914 (144): 1–40, doi : 10.1515/crll.1914.144.1 , MR   1580890 , S2CID   122998337
• Талман, Луи А. (1977), «Неподвижные точки для уплотнения мультифункций в метрических пространствах с выпуклой структурой» , Отчеты математического семинара Кодай , 29 (1–2): 62–70, MR   0463985
• Туссен, Годфрид (1983), «Решение геометрических задач с помощью вращающихся штангенциркулей», Труды IEEE MELECON '83, Афины , CiteSeerX   10.1.1.155.5671
• Туссен, Годфрид (1986), «Оптимальный алгоритм вычисления относительной выпуклой оболочки набора точек многоугольника», Труды EURASIP, Обработка сигналов III: Теории и приложения, Часть 2 , Северная Голландия, стр. 853– 856
• Уикс, Джеффри Р. (1993), «Выпуклые оболочки и изометрии гиперболических трехмерных многообразий с точками возврата», Топология и ее приложения , 52 (2): 127–149, doi : 10.1016/0166-8641(93)90032-9 , МР   1241189
• Вестерманн, LRJ (1976), «Об операторе корпуса», Mathematical Inquiries , 38 (2): 179–184, doi : 10.1016/1385-7258(76)90065-2 , MR   0404097
• Уайт, Ф. Пьюрьер (апрель 1923 г.), «Чистая математика», Science Progress in the Twentieth Century , 17 (68): 517–526, JSTOR   43432008.
• Уитли, Роберт (1986), «Теорема Крейна-Шмулиана», Труды Американского математического общества , 97 (2): 376–377, doi : 10.2307/2046536 , JSTOR   2046536 , MR   0835903
• Уильямс, Джейсон; Россиньяк, Ярек (2005), «Затягивание: морфологическое упрощение, ограничивающее кривизну», в Коббелте, Лейф; Шапиро, Вадим (ред.), Труды десятого симпозиума ACM по твердотельному и физическому моделированию, 2005 г., Кембридж, Массачусетс, США, 13–15 июня 2005 г. , ACM, стр. 107–112, doi : 10.1145/1060244.1060257 , hdl : 1853/3736 , S2CID   15514388
• Уортон, Брюс Дж. (1995), «Оценщик размера домашнего диапазона на основе выпуклой оболочки», Biometrics , 51 (4): 1206–1215, doi : 10.2307/2533254 , JSTOR   2533254

Внешние ссылки

• «Выпуклая оболочка» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. , «Выпуклая оболочка» , MathWorld
• «Выпуклая оболочка» Эрика В. Вайсштейна , Демонстрационный проект Wolfram , 2007 г.