Выпуклый корпус - Convex hull

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

Выпуклый корпус красного набора - это синий и красный выпуклый набор.

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

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

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

Определения

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

Набор точек в Евклидово пространство определяется как выпуклый если он содержит отрезки прямых, соединяющие каждую пару его точек. Выпуклая оболочка данного множества ${\displaystyle X}$ можно определить как^[1]

1. (Единственное) минимальное выпуклое множество, содержащее ${\displaystyle X}$
2. Пересечение всех выпуклых множеств, содержащих ${\displaystyle X}$
3. Набор всех выпуклые комбинации очков в ${\displaystyle X}$
4. Союз всех симплексы с вершинами в ${\displaystyle X}$

За ограниченные множества в евклидовой плоскости, а не все на одной прямой, граница выпуклой оболочки - это простая замкнутая кривая с минимумом периметр содержащий ${\displaystyle X}$. Можно представить себе растяжение резинка так что он окружает весь набор ${\displaystyle S}$ а затем отпустив его, позволив ему сжаться; когда он становится туго натянутым, он охватывает выпуклую оболочку ${\displaystyle S}$.^[2] Эта формулировка не сразу распространяется на более высокие измерения: для конечного набора точек в трехмерном пространстве окрестность остовное дерево точек окружает их сколь угодно малой площадью поверхности, меньшей, чем площадь поверхности выпуклой оболочки.^[3] Однако в более высоких измерениях варианты проблема препятствия нахождения поверхности с минимальной энергией над заданной формой может иметь выпуклую оболочку в качестве своего решения.^[4]

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

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

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

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

Каждое выпуклое множество, содержащее ${\displaystyle X}$ должен (по предположению, что он выпуклый) содержать все выпуклые комбинации точек из ${\displaystyle X}$, поэтому множество всех выпуклых комбинаций содержится в пересечении всех выпуклых множеств, содержащих ${\displaystyle X}$. Наоборот, множество всех выпуклых комбинаций само является выпуклым множеством, содержащим ${\displaystyle X}$, поэтому он также содержит пересечение всех выпуклых множеств, содержащих ${\displaystyle X}$, поэтому второе и третье определения эквивалентны.^[6]

Фактически, согласно Теорема Каратеодори, если ${\displaystyle X}$ является подмножеством ${\displaystyle d}$-мерное евклидово пространство, любая выпуклая комбинация конечного числа точек из ${\displaystyle X}$ также является выпуклой комбинацией не более чем ${\displaystyle d+1}$ указывает в ${\displaystyle X}$. Множество выпуклых комбинаций ${\displaystyle (d+1)}$-набор точек есть симплекс; в самолете это треугольник а в трехмерном пространстве это тетраэдр. Следовательно, всякая выпуклая комбинация точек ${\displaystyle X}$ принадлежит симплексу, вершины которого принадлежат ${\displaystyle X}$, а третье и четвертое определения эквивалентны.^[6]

Верхняя и нижняя части корпуса

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

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

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

В замкнутая выпуклая оболочка набора это закрытие выпуклой оболочки, а открытая выпуклая оболочка это интерьер (или в некоторых источниках относительный интерьер ) выпуклой оболочки.^[8]

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

Если открытая выпуклая оболочка множества ${\displaystyle X}$ является ${\displaystyle d}$-мерной, то каждая точка оболочки принадлежит открытой выпуклой оболочке не более чем ${\displaystyle 2d}$ точки ${\displaystyle X}$. Множества вершин квадрата, правильного октаэдра или многомерного кросс-многогранник приведите примеры, где именно ${\displaystyle 2d}$ очки нужны.^[10]

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

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

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

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

(набор точек, лежащих на или выше ведьма Аньези ) имеет открытый верхняя полуплоскость как его выпуклая оболочка.^[12]

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

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

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

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

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

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

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

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

Применительно к конечному набору точек это оператор замыкания антиматроид - обстреливающий антиматроид множества точек. Каждый антиматроид может быть представлен таким образом выпуклой оболочкой точек в евклидовом пространстве достаточно высокой размерности.^[17]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Космические кривые

An олоид, выпуклая оболочка двух окружностей в трехмерном пространстве

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

Функции

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

Выпуклая оболочка или нижняя выпуклая оболочка функции ${\displaystyle f}$ в реальном векторном пространстве - это функция, эпиграф - выпуклая нижняя оболочка надграфа ${\displaystyle f}$.Это единственный максимальный выпуклая функция мажоритарный ${\displaystyle f}$.^[29] Определение может быть расширено до выпуклой оболочки набора функций (полученной из выпуклой оболочки объединения их надграфов или, что то же самое, из их поточечного минимума), и в этой форме оно двойственно выпуклый сопряженный операция.^[30]

Вычисление

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

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

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

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

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

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

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

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

• В аффинная оболочка наименьшее аффинное подпространство евклидова пространства, содержащее данное множество, или объединение всех аффинных комбинаций точек в множестве.^[38]
• В линейный корпус наименьшее линейное подпространство векторного пространства, содержащего данный набор, или объединение всех линейных комбинаций точек в наборе.^[38]
• В конический корпус или положительная оболочка подмножества векторного пространства - это множество всех положительных комбинаций точек в подмножестве.^[38]
• В визуальный корпус трехмерного объекта по отношению к набору точек обзора состоит из точек ${\displaystyle p}$ так что каждый луч с точки зрения через ${\displaystyle p}$ пересекает объект. Эквивалентно это пересечение (невыпуклых) конусов, образованных контуром объекта по отношению к каждой точке обзора. Он используется в 3D реконструкция как самая большая фигура, которая может иметь те же очертания с заданных точек обзора.^[39]
• Круглая оболочка или альфа-оболочка подмножества плоскости - это пересечение всех дисков с заданным радиусом. ${\displaystyle 1/\alpha }$ которые содержат подмножество.^[40]
• В относительная выпуклая оболочка подмножества двумерного простой многоугольник является пересечением всех относительно выпуклых надмножеств, где множество внутри одного многоугольника является относительно выпуклым, если оно содержит геодезический между любыми двумя его точками.^[41]
• В ортогональная выпуклая оболочка или прямолинейная выпуклая оболочка - это пересечение всех ортогонально выпуклых и связанных надмножеств, где набор является ортогонально выпуклым, если он содержит все параллельные оси сегменты между парами его точек.^[42]
• Ортогональная выпуклая оболочка - это частный случай гораздо более общей конструкции: гипервыпуклая оболочка, который можно рассматривать как самый маленький инъективное метрическое пространство содержащий точки данного метрическое пространство.^[43]
• В голоморфно выпуклая оболочка является обобщением подобных понятий на комплексные аналитические многообразия, полученная как пересечение множеств подуровней голоморфные функции содержащий данный набор.^[44]

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

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

Приложения

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

Математика

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

Полигоны Ньютона одномерного многочлены и Многогранники Ньютона многомерных многочленов представляют собой выпуклые оболочки точек, полученные из показателей степени членов многочлена, и могут использоваться для анализа асимптотический поведение многочлена и оценки его корней.^[48] Выпуклые оболочки и многочлены также объединяются в Теорема Гаусса – Лукаса, согласно которому корни производной многочлена все лежат внутри выпуклой оболочки корней многочлена.^[49]

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

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

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

Статистика

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

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

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

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

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

Экономика

в Модель Эрроу – Дебре из общее экономическое равновесие, агенты предполагаются выпуклыми бюджетные наборы и выпуклые предпочтения. Эти предположения выпуклость в экономике могут быть использованы для доказательства существования равновесия. невыпуклый, его можно сделать выпуклым, взяв выпуклые оболочки. Теорема Шепли – Фолкмана может использоваться, чтобы показать, что для крупных рынков это приближение является точным и приводит к «квазиравновесию» для исходного невыпуклого рынка.^[59]

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

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

В геометрии лодки и конструкции корабля, обхват цепи является мерой размера парусного судна, определяемой с использованием выпуклого корпуса поперечного сечения корпус судна. Он отличается от обхват кожи, периметр самого поперечного сечения, за исключением лодок и кораблей с выпуклым корпусом.^[61]

Этология

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

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

В квантовая физика, то пространство состояний любой квантовой системы - совокупность всех способов подготовки системы - представляет собой выпуклую оболочку, крайние точки которой положительно-полуопределенные операторы известны как чистые состояния, а внутренние точки - смешанными состояниями.^[65] В Теорема Шредингера – HJW доказывает, что любое смешанное состояние может быть записано как выпуклая комбинация чистых состояний несколькими способами.^[66]

История

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

Примечания

1. Рокафеллар (1970), п. 12.
2. de Berg et al. (2008), п. 3.
3. Уильямс и Россиньяк (2005). См. Также Дуглас Заре, ответ на «периметр невыпуклого множества», MathOverflow, 16 мая 2014 г.
4. Оберман (2007).
5. Кнут (1992).
6. Рокафеллар (1970), п. 12; Лэй (1982), п. 17.
7. de Berg et al. (2008), п. 6. Идея разделения корпуса на две цепи исходит из эффективного варианта Сканирование Грэма к Эндрю (1979).
8. Зонтаг (1982).
9. Рокафеллар (1970), п. 99.
10. Стейниц (1914); Гастин (1947); Барани, Качальски и Пах (1982)
11. Грюнбаум (2003), п. 16; Лэй (1982), п. 21; Сакума (1977).
12. Этот пример приводится Талман (1977), Замечание 2.6.
13. Уитли (1986).
14. Крейн и Мильман (1940); Лэй (1982), п. 43.
15. Окон (2000).
16. Кисельман (2002).
17. Кашивабара, Накамура и Окамото (2005).
18. Крейн и Шмулиан (1940), Теорема 3, страницы 562–563; Шнайдер (1993), Теорема 1.1.2 (стр. 2–3) и глава 3.
19. de Berg et al. (2008), п. 254.
20. Грюнбаум (2003), п. 57.
21. де Берг и др. (2008), п. 256.
22. de Berg et al. (2008), п. 245.
23. Раппопорт (1992).
24. Demaine et al. (2008).
25. Крэнстон, Сюй и Марч (1989).
26. Седых (1981).
27. Дирнбёк и Стачел (1997).
28. Ситон (2017).
29. Рокафеллар (1970), п. 36.
30. Рокафеллар (1970), п. 149.
31. Авис, Бремнер и Зайдель (1997).
32. de Berg et al. (2008), п. 13.
33. Шазель (1993); de Berg et al. (2008), п. 256.
34. Маккаллум и Авис (1979); Грэм и Яо (1983); Ли (1983).
35. Чан (2012).
36. Баш, Гибас и Хершбергер (1999).
37. Туссен (1983).
38. Вестерманн (1976).
39. Лаурентини (1994).
40. Эдельсбруннер, Киркпатрик и Зайдель (1983).
41. Туссен (1986).
42. Оттманн, Сойсалон-Сойнинен и Вуд (1984).
43. Херрлих (1992).
44. Росси (1961).
45. Коричневый (1979).
46. Шазель (1985).
47. Чанг и Яп (1986).
48. Артин (1967); Гельфанд, Капранов и Зелевинский (1994)
49. Прасолов (2004).
50. Джонсон (1976).
51. Гарднер (1984).
52. Рей (1979).
53. Эпштейн и Марден (1987).
54. Недели (1993).
55. Руссеу, Рутс и Тьюки (1999).
56. Харрис (1971).
57. Pulleyblank (1983); см. особенно замечания после теоремы 2.9.
58. Като (1992).
59. Никола (2000). См., В частности, Раздел 16.9, Невыпуклость и приблизительное равновесие, стр. 209–210.
60. Чен и Ван (2003).
61. Мейсон (1908).
62. Кернохан, Гитцен и Миллспо (2001), п. 137–140; Нильсен, Педерсен и Линнелл (2008)
63. Вортон (1995).
64. Getz & Wilmers (2004).
65. Риффель и Полак (2011).
66. Киркпатрик (2006).
67. Ньютон (1676); видеть Ауэль (2019), стр. 336, и Эскобар и Каве (2020).
68. См., Например, Белый (1923), стр.520.
69. Обедает (1938).

Рекомендации

• Эндрю, А. М. (1979), "Другой эффективный алгоритм для выпуклых оболочек в двух измерениях", Письма об обработке информации, 9 (5): 216–219, Дои:10.1016/0020-0190(79)90072-3
• Артин, Эмиль (1967), «2.5. Многоугольник Ньютона», Алгебраические числа и алгебраические функции, Гордон и Брич, стр. 37–43, МИСТЕР  0237460
• Ауэль, Ашер (2019), «Математика Грейс Мюррей Хоппер» (PDF), Уведомления Американского математического общества, 66 (3): 330–340, МИСТЕР  3889348
• Авис, Дэвид; Бремнер, Дэвид; Зайдель, Раймунд (1997), "Насколько хороши алгоритмы выпуклой оболочки?", Вычислительная геометрия, 7 (5–6): 265–301, Дои:10.1016 / S0925-7721 (96) 00023-5, МИСТЕР  1447243
• Барань, Имре; Качальски, Меир; Пах, Янош (1982), «Количественные теоремы типа Хелли», Труды Американского математического общества, 86 (1): 109–114, Дои:10.2307/2044407, МИСТЕР  0663877
• Баш, Жюльен; Гибас, Леонидас Дж.; Хершбергер, Джон (1999), «Структуры данных для мобильных данных», Журнал алгоритмов, 31 (1): 1–28, CiteSeerX  10.1.1.134.6921, Дои:10.1006 / jagm.1998.0988, МИСТЕР  1670903
• Биркофф, Гарретт (1935), «Интегрирование функций со значениями в банаховом пространстве», Труды Американского математического общества, 38 (2): 357–378, Дои:10.2307/1989687, МИСТЕР  1501815
• Браун, К. К. (1979), "Диаграммы Вороного из выпуклой оболочки", Письма об обработке информации, 9 (5): 223–228, Дои:10.1016/0020-0190(79)90074-7
• де Берг, М.; ван Кревельд, М.; Овермарс, Марк; Шварцкопф, О. (2008), Вычислительная геометрия: алгоритмы и приложения (3-е изд.), Springer
• Чан, Тимоти М. (2012), «Три задачи о динамических выпуклых оболочках», Международный журнал вычислительной геометрии и приложений, 22 (4): 341–364, Дои:10.1142 / S0218195912600096, МИСТЕР  2994585
• Chang, J. S .; Яп, Ч.-К. (1986), "Полиномиальное решение задачи очистки картофеля", Дискретная и вычислительная геометрия, 1 (2): 155–182, Дои:10.1007 / BF02187692, МИСТЕР  0834056
• Шазель, Бернар (1985), «О выпуклых слоях плоского множества», IEEE Transactions по теории информации, 31 (4): 509–517, Дои:10.1109 / TIT.1985.1057060, МИСТЕР  0798557
• Шазель, Бернар (1993), «Оптимальный алгоритм выпуклой оболочки в любой фиксированной размерности» (PDF), Дискретная и вычислительная геометрия, 10 (1): 377–409, CiteSeerX  10.1.1.113.8709, Дои:10.1007 / BF02573985
• Чен, Цинюй; Ван, Гочжао (март 2003 г.), «Класс кривых, подобных Безье», Компьютерный геометрический дизайн, 20 (1): 29–39, Дои:10.1016 / s0167-8396 (03) 00003-7
• Cranston, M .; Hsu, P .; Марч, П. (1989), "Гладкость выпуклой оболочки плоского броуновского движения", Анналы вероятности, 17 (1): 144–150, JSTOR  2244202, МИСТЕР  0972777
• Демейн, Эрик Д.; Гассенд, Блэз; О'Рурк, Джозеф; Туссен, Годфрид Т. (2008), «Все полигоны бесконечно переворачиваются ... верно?», Обзоры по дискретной и вычислительной геометрии, Современная математика, 453, Провиденс, Род-Айленд: Американское математическое общество, стр. 231–255, Дои:10.1090 / conm / 453/08801, МИСТЕР  2405683
• Дайнс, Л.Л. (1938), «О выпуклости», Американский математический ежемесячный журнал, 45 (4): 199–209, Дои:10.2307/2302604, JSTOR  2302604, МИСТЕР  1524247
• Дирнбек, Ганс; Стахель, Хельмут (1997), «Развитие олоида» (PDF), Журнал геометрии и графики, 1 (2): 105–118, МИСТЕР  1622664
• Эдельсбруннер, Герберт; Киркпатрик, Дэвид Г.; Зайдель, Раймунд (1983), «О форме множества точек на плоскости», IEEE Transactions по теории информации, 29 (4): 551–559, Дои:10.1109 / TIT.1983.1056714
• Эпштейн, Д. Б. А.; Марден, А. (1987), «Выпуклые оболочки в гиперболическом пространстве, теорема Салливана и измеренные гофрированные поверхности», в Эпштейн, Д. Б. А. (ред.), Аналитические и геометрические аспекты гиперболического пространства (Ковентри / Дарем, 1984), Серия лекций Лондонского математического общества, 111, Кембридж: Издательство Кембриджского университета, стр. 113–253, МИСТЕР  0903852
• Эскобар, Лаура; Каве, Киумарс (сентябрь 2020 г.), «Выпуклые многогранники, алгебраическая геометрия и комбинаторика» (PDF), Уведомления Американского математического общества, 67 (8): 1116–1123
• Гарднер, Л. Террелл (1984), "Элементарное доказательство теоремы Руссо-Дая", Труды Американского математического общества, 90 (1): 171, Дои:10.2307/2044692, МИСТЕР  0722439
• Гельфанд, И.М.; Капранов, М.М.; Зелевинский, А.В. (1994), "6. Многогранники Ньютона и многогранники Чоу", Дискриминанты, результаты и многомерные детерминанты, Математика: теория и приложения, Биркхойзер, стр. 193–213, Дои:10.1007/978-0-8176-4771-1, ISBN  0-8176-3660-9, МИСТЕР  1264417
• Getz, Wayne M .; Уилмерс, Кристофер С. (2004), «Локальная конструкция ближайшего соседа с выпуклым корпусом жилых комплексов и распределения использования» (PDF), Экография, Wiley, 27 (4): 489–505, Дои:10.1111 / j.0906-7590.2004.03835.x
• Грэм, Рональд Л.; Яо, Ф. Фрэнсис (1983), "Нахождение выпуклой оболочки простого многоугольника", Журнал алгоритмов, 4 (4): 324–331, Дои:10.1016/0196-6774(83)90013-5, МИСТЕР  0729228
• Грюнбаум, Бранко (2003), Выпуклые многогранники, Тексты для выпускников по математике, 221 (2-е изд.), Springer, ISBN  9780387004242
• Гастин, Уильям (1947), "О внутренней части выпуклой оболочки евклидова множества", Бюллетень Американского математического общества, 53: 299–301, Дои:10.1090 / S0002-9904-1947-08787-5, МИСТЕР  0020800
• Харрис, Бернард (1971), «Математические модели для теории статистических решений» (PDF), Методы оптимизации в статистике (Proc. Sympos., Ohio State Univ., Columbus, Ohio, 1971), стр. 369–389, МИСТЕР  0356305
• Херрлих, Хорст (1992), "Гипервыпуклые оболочки метрических пространств", Труды симпозиума по общей топологии и приложениям (Оксфорд, 1989), Топология и ее приложения, 44 (1–3): 181–187, Дои:10.1016 / 0166-8641 (92) 90092-E, МИСТЕР  1173256
• Джонсон, Чарльз Р. (1976), «Нормальность и числовой диапазон», Линейная алгебра и ее приложения, 15 (1): 89–94, Дои:10.1016 / 0024-3795 (76) 90080-х, МИСТЕР  0460358
• Кашивабара, Кенджи; Накамура, Масатака; Окамото, Йошио (2005), "Теорема аффинного представления для абстрактных выпуклых геометрий", Вычислительная геометрия, 30 (2): 129–144, CiteSeerX  10.1.1.14.4965, Дои:10.1016 / j.comgeo.2004.05.001, МИСТЕР  2107032
• Като, Наоки (1992), "Бикритериальные задачи оптимизации сети", IEICE Trans. Основы электроники, связи и компьютерных наук, E75-A: 321–329
• Кернохан, Брайан Дж .; Гитцен, Роберт А.; Миллспо, Джошуа Дж. (2001), «Анализ использования пространства и перемещений животных», Миллспо, Джошуа; Марзлафф, Джон М. (ред.), Радио слежение и популяции животных, Academic Press, ISBN  9780080540221
• Киркпатрик, К. А. (2006), "Теорема Шредингера – HJW", Основы письма по физике, 19 (1): 95–102, arXiv:Quant-ph / 0305068, Дои:10.1007 / s10702-006-1852-1
• Кисельман, Кристер О. (2002), "Полугруппа операторов в теории выпуклости", Труды Американского математического общества, 354 (5): 2035–2053, Дои:10.1090 / S0002-9947-02-02915-X, МИСТЕР  1881029
• Кнут, Дональд Э. (1992), Аксиомы и оболочки, Конспект лекций по информатике, 606, Гейдельберг: Springer-Verlag, Дои:10.1007/3-540-55611-7, ISBN  3-540-55611-7, МИСТЕР  1226891
• Кениг, Денес (Декабрь 1922 г.), "Über konvexe Körper", Mathematische Zeitschrift, 14 (1): 208–210, Дои:10.1007 / bf01215899; см. также обзор Ганс Радемахер (1922), JFM  48.0835.01
• Крейн, Марк; Мильман, Дэвид (1940), «О крайних точках правильных выпуклых множеств», Studia Mathematica, 9: 133–138
• Крейн, М.; Шмулян В. (1940), "О правильно выпуклых множествах в пространстве, сопряженном с банаховым пространством", Анналы математики, Вторая серия, 41: 556–583, Дои:10.2307/1968735, HDL:10338.dmlcz / 100106, JSTOR  1968735, МИСТЕР  0002009
• Лаурентини, А. (1994), "Визуальная концепция корпуса для понимания изображения на основе силуэта", IEEE Transactions по анализу шаблонов и машинному анализу, 16 (2): 150–162, Дои:10.1109/34.273735
• Лэй, Стивен Р. (1982), Выпуклые множества и их приложения, Джон Уайли и сыновья, ISBN  0-471-09584-2, МИСТЕР  0655598
• Ли, Д. Т. (1983), «О нахождении выпуклой оболочки простого многоугольника», Международный журнал компьютерных и информационных наук, 12 (2): 87–98, Дои:10.1007 / BF00993195, МИСТЕР  0724699
• Мейсон, Герберт Б. (1908), Энциклопедия кораблей и судоходства, п. 698
• Маккаллум, Дункан; Авис, Дэвид (1979), "Линейный алгоритм поиска выпуклой оболочки простого многоугольника", Письма об обработке информации, 9 (5): 201–206, Дои:10.1016/0020-0190(79)90069-3, МИСТЕР  0552534
• Ньютон, Исаак (24 октября 1676 г.), "Письмо Генри Ольденбургу", Проект Ньютон, Оксфордский университет
• Никола, Пьеркарло (2000), «Общее конкурентное равновесие», Мейнстрим математической экономики в 20 веке, Springer, стр. 197–215, Дои:10.1007/978-3-662-04238-0_16
• Nilsen, Erlend B .; Педерсен, Симен; Линнелл, Джон Д. С. (2008), «Можно ли использовать дома с минимальным выпуклым многоугольником для получения биологически значимых выводов?», Экологические исследования, 23 (3): 635–639, Дои:10.1007 / s11284-007-0421-9
• Оберман, Адам М. (2007), «Выпуклая оболочка - решение нелинейной проблемы с препятствиями», Труды Американского математического общества, 135 (6): 1689–1694, Дои:10.1090 / S0002-9939-07-08887-9, МИСТЕР  2286077
• Окон, Т. (2000), "Теория Шоке в метрических пространствах", Zeitschrift für Analysis und ihre Anwendungen, 19 (2): 303–314, Дои:10.4171 / ZAA / 952, МИСТЕР  1768994
• Оттманн, Т .; Soisalon-Soininen, E .; Вуд, Дерик (1984), "Об определении и вычислении прямолинейных выпуклых оболочек", Информационные науки, 33 (3): 157–171, Дои: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
• Pulleyblank, W. R. (1983), «Многогранная комбинаторика», в Bachem, Achim; Корте, Бернхард; Grötschel, Мартин (ред.), Математическое программирование: современное состояние (XI Международный симпозиум по математическому программированию, Бонн, 1982 г.), Springer, стр. 312–345, Дои:10.1007/978-3-642-68874-4_13
• Раппопорт, Ари (1992), "Эффективный адаптивный алгоритм для построения выпуклого дерева разностей простого многоугольника", Форум компьютерной графики, 11 (4): 235–240, Дои:10.1111/1467-8659.1140235
• Рэй, Джон Р. (1979), "Некоторые обобщения теоремы Тверберга", Израильский математический журнал, 34 (3): 238–244 (1980), Дои:10.1007 / BF02760885, МИСТЕР  0570883
• Риффель, Элеонора Г.; Полак, Вольфганг Х. (2011), Квантовые вычисления: краткое введение, MIT Press, стр. 215–216, ISBN  978-0-262-01506-6
• Рокафеллар, Р. Тиррелл (1970), Выпуклый анализ, Принстонская математическая серия, 28, Принстон, Нью-Джерси: Издательство Принстонского университета, МИСТЕР  0274683
• Росси, Хьюго (1961), "Голоморфно выпуклые множества нескольких комплексных переменных", Анналы математики, Вторая серия, 74: 470–493, Дои:10.2307/1970292, JSTOR  1970292, МИСТЕР  0133479
• Руссей, Питер Дж.; Рутс, Ида; Тьюки, Джон У. (1999), "Заговор на волынках: Двумерный коробочный сюжет", Американский статистик, 53 (4): 382–387, Дои:10.1080/00031305.1999.10474494
• Сакума, Ицуо (1977), "Замкнутость выпуклых оболочек", Журнал экономической теории, 14 (1): 223–227, Дои:10.1016/0022-0531(77)90095-3
• Шнайдер, Рольф (1993), Выпуклые тела: теория Брунна – Минковского., Энциклопедия математики и ее приложений, 44, Кембридж: Издательство Кембриджского университета, Дои:10.1017 / CBO9780511526282, ISBN  0-521-35220-7, МИСТЕР  1216521
• Ситон, Кэтрин А. (2017), «Сферироны и D-формы: связанная крючком связь», Журнал математики и искусств, 11 (4): 187–202, arXiv:1603.08409, Дои:10.1080/17513472.2017.1318512, МИСТЕР  3765242
• Седых, В. Д. (1981), "Структура выпуклой оболочки пространственной кривой", Труды семинара имени И. Г. Петровского (6): 239–256, МИСТЕР  0630708, переведено на Журнал советской математики 33 (4): 1140–1153, 1986, Дои:10.1007 / BF01086114
• Зонтаг, Эдуардо Д. (1982), «Замечания по кусочно-линейной алгебре», Тихоокеанский математический журнал, 98 (1): 183–201, МИСТЕР  0644949
• Стейниц, Э. (1914), "Bedingt konvergente Reihen und konvexe Systeme. (Fortsetzung)", Journal für die Reine und Angewandte Mathematik, 144: 1–40, Дои:10.1515 / crll.1914.144.1, МИСТЕР  1580890
• Талман, Луи А. (1977), «Неподвижные точки уплотняющих мультифункций в метрических пространствах с выпуклой структурой», Отчеты математического семинара Кодаи, 29 (1–2): 62–70, МИСТЕР  0463985
• Туссен, Годфрид (1983), «Решение геометрических задач с вращающимися штангенциркулями», Протоколы IEEE MELECON '83, Афины, CiteSeerX  10.1.1.155.5671
• Туссен, Годфрид (1986), «Оптимальный алгоритм для вычисления относительной выпуклой оболочки множества точек в многоугольнике», Труды EURASIP, Обработка сигналов III: Теории и приложения, Часть 2, Северная Голландия, стр. 853–856.
• Уикс, Джеффри Р. (1993), "Выпуклые оболочки и изометрии трехмерных гиперболических многообразий с каспами", Топология и ее приложения, 52 (2): 127–149, Дои:10.1016/0166-8641(93)90032-9, МИСТЕР  1241189
• Вестерманн, Л. Р. Дж. (1976), "Об операторе оболочки", Indagationes Mathematicae, 38 (2): 179–184, Дои:10.1016/1385-7258(76)90065-2, МИСТЕР  0404097
• Уайт, Ф. Пурьер (апрель 1923 г.), «Чистая математика», Научный прогресс в двадцатом веке, 17 (68): 517–526, JSTOR  43432008
• Уитли, Роберт (1986), "Теорема Крейна-Шмулиана", Труды Американского математического общества, 97 (2): 376–377, Дои:10.2307/2046536, МИСТЕР  0835903
• Уильямс, Джейсон; Rossignac, Jarek (2005), "Tightening: curvature-limiting morphological simplification", in Kobbelt, Leif; Shapiro, Vadim (eds.), Proceedings of the Tenth ACM Symposium on Solid and Physical Modeling 2005, Cambridge, Massachusetts, USA, June 13-15, 2005, ACM, pp. 107–112, Дои:10.1145/1060244.1060257, HDL:1853/3736
• Worton, Bruce J. (1995), "A convex hull-based estimator of home-range size", Биометрия, 51 (4): 1206–1215, Дои:10.2307/2533254, JSTOR  2533254

внешняя ссылка

• "Convex hull", Энциклопедия математики, EMS Press, 2001 [1994]
• Вайсштейн, Эрик В., "Convex Hull", MathWorld
• "Convex Hull" к Эрик В. Вайсштейн, Вольфрам Демонстрационный проект, 2007.