Выпуклый корпус

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

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

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

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

Определения [ править ]

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

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

(Единственное) минимальное выпуклое множество, содержащее ${\ displaystyle X}$
Пересечение всех выпуклых множеств, содержащих ${\ displaystyle X}$
Множество всех выпуклых комбинаций точек в ${\ displaystyle X}$
Объединение всех симплексов с вершинами из ${\ displaystyle X}$

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

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

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

Трехмерная выпуклая оболочка облака из 120 точек

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

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

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

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

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

Топологические свойства [ править ]

Закрытые и открытые корпуса [ править ]

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

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

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

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

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

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

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

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

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

Крайние точки [ править ]

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

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

Оператор закрытия [ править ]

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

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

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

Сумма Минковского [ править ]

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

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

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

Особые случаи [ править ]

Наборы конечных точек [ править ]

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

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

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

Простые многоугольники [ править ]

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

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

Броуновское движение [ править ]

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

Космические кривые [ править ]

Oloid , выпуклая оболочка двух окружностей в 3D пространстве

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

Функции [ править ]

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

Вычисление [ править ]

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

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

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

Связанные структуры [ править ]

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

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

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

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

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

Приложения [ править ]

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

Математика [ править ]

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

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

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

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

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

Статистика [ править ]

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

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

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

Комбинаторная оптимизация [ править ]

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

Экономика [ править ]

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

Геометрическое моделирование [ править ]

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

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

Этология [ править ]

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

Квантовая физика [ править ]

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

История [ править ]

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

Заметки [ править ]

^ a b Рокафеллар (1970) , стр. 12.
^ а б в де Берг и др. (2008) , стр. 3.
^ Уильямс и Россиньяк (2005) . См. Также Дуглас Заре, ответ на «периметр невыпуклого множества» , MathOverflow , 16 мая 2014 г.
^ Oberman (2007) .
^ Кнут (1992) .
^ a b Рокафеллар (1970) , стр. 12; Lay (1982) , стр. 17.
^ де Берг и др. (2008) , стр. 6. Идея разделения корпуса на две цепи происходит от эффективного варианта Graham сканирования по Эндрю (1979) .
^ Зонтаг (1982) .
^ Рокафеллар (1970) , стр. 99.
^ Стейниц (1914) ; Густин (1947) ; Барань, Качальски и Пах (1982)
^ Grünbaum (2003) , стр. 16; Lay (1982) , стр. 21; Сакума (1977) .
^ Этот пример приводится Талманом (1977) , замечание 2.6.
^ Уитли (1986) .
^ Крейн и Милман (1940) ; Lay (1982) , стр. 43.
^ Окна (2000) .
^ Kiselman (2002) .
^ Kashiwabara, Nakamura & Okamoto (2005) .
^ Крейна и Шмульяна (1940) , теорема 3, страницы 562-563; Шнайдер (1993) , теорема 1.1.2 (страницы 2–3) и глава 3.
^ де Берг и др. (2008) , стр. 254.
^ Grünbaum (2003) , стр. 57.
^ де Берг и др. (2008) , стр. 256.
^ де Берг и др. (2008) , стр. 245.
^ Раппопорт (1992) .
^ Demaine et al. (2008) .
^ Крэнстон, Hsu & March (1989) .
↑ Седых (1981) .
^ Dirnböck & Stachel (1997) .
^ Ситон (2017) .
^ Рокафеллар (1970) , стр. 36.
^ Рокафеллар (1970) , стр. 149.
^ Avis, Бремнер и Сайдел (1997) .
^ де Берг и др. (2008) , стр. 13.
^ Chazelle (1993) ; де Берг и др. (2008) , стр. 256.
^ МакКаллум и Авис (1979) ; Грэм и Яо (1983) ; Ли (1983) .
^ Чан (2012) .
^ Баш, Guibas & Хершбергер (1999) .
Перейти ↑ Toussaint (1983) .
^ a b c Вестерманн (1976) .
^ Лаурентини (1994) .
^ а б Эдельсбруннер, Киркпатрик и Зайдель (1983) .
Перейти ↑ Toussaint (1986) .
^ Ottmann, Soisalon-Soininen & Wood (1984) .
^ Herrlich (1992) .
^ Росси (1961) .
^ Браун (1979) .
^ Chazelle (1985) .
^ Чанг и Яп (1986) .
^ Артин (1967) ; Гельфанд, Капранов и Зелевинский (1994)
↑ Прасолов (2004) .
^ Джонсон (1976) .
^ Гарднер (1984) .
^ Reay (1979) .
↑ Эпштейн и Марден (1987) .
^ Недели (1993) .
^ Rousseeuw, Колея и Тьюки (1999) .
^ Харрис (1971) .
^ Pulleyblank (1983) ; см. особенно замечания после теоремы 2.9.
^ Като (1992) .
^ Никола (2000) . См., В частности, Раздел 16.9, Невыпуклость и приблизительное равновесие, стр. 209–210.
^ Чен и Ван (2003) .
^ Мейсон (1908) .
^ Kernohan, Gitzen & Millspaugh (2001) , стр. 137–140; Нильсен, Педерсен и Линнелл (2008)
^ Worton (1995) .
^ Getz & Wilmers (2004) .
^ Риффель & Полак (2011) .
^ Киркпатрик (2006) .
^ Ньютон (1676) ; см. Auel (2019) , стр. 336, и Escobar & Kaveh (2020) .
^ См., Например, White (1923) , стр. 520.
^ Dines (1938) .

Ссылки [ править ]

Эндрю, А. М. (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, MR 3889348
Авис, Дэвид ; Бремнер, Дэвид; Зайдель, Раймунд (1997), "Как хорошо выпуклые алгоритмы корпуса?", Вычислительная геометрия , 7 (5-6): 265-301, DOI : 10.1016 / S0925-7721 (96) 00023-5 , MR 1447243
Барани, Имре ; Качальски, Меир; Pach, Янош (1982), "Теоремы Количественный типа Хелли", Труды Американского математического общества , 86 (1): 109-114, DOI : 10,2307 / 2044407 , MR 0663877
Баш, Жюльен; Гибас, Леонидас Дж .; Хершбергер, Джон (1999), "Структуры данных для мобильных данных", журнал алгоритмов , 31 (1): 1-28, CiteSeerX 10.1.1.134.6921 , DOI : 10,1006 / jagm.1998.0988 , МР 1670903
Биркгофу, Garrett (1935), "Интеграция функций со значениями в банаховом пространстве", Труды Американского математического общества , 38 (2): 357-378, DOI : 10,2307 / 1989687 , MR 1501815
Браун, KQ (1979), «Диаграммы Вороного из выпуклой оболочки», Письма об обработке информации , 9 (5): 223–228, DOI : 10.1016 / 0020-0190 (79) 90074-7
де Берг, М .; ван Кревельд, М .; Овермарс, Марк ; Шварцкопф О. (2008), Вычислительная геометрия: алгоритмы и приложения (3-е изд.), Springer
Чан, Тимоти М. (2012), "Три задача о динамических выпуклых оболочках", Международный журнал вычислительной геометрии и приложений , 22 (4): 341-364, DOI : 10,1142 / S0218195912600096 , МР 2994585
Чанг, JS; Яп, Ч.-К. (1986), "Полином решения проблемы картофельной-пилинг", Дискретная и вычислительная геометрия , 1 (2): 155-182, DOI : 10.1007 / BF02187692 , MR 0834056
Chazelle, Бернар (1985), "О выпуклых слоев плоского множества", IEEE Transactions по теории информации , 31 (4): 509-517, DOI : 10,1109 / TIT.1985.1057060 , МР 0798557
Chazelle, Бернар (1993), "Оптимальная выпуклая оболочка алгоритма в любой фиксированной размерности" (PDF) , дискретное и Вычислительная геометрия , 10 (1): 377-409, CiteSeerX 10.1.1.113.8709 , DOI : 10.1007 / BF02573985
Чен, Циньюй; Ван, Guozhao (март 2003), "Класс Безье типа кривых", Computer Aided Design Геометрический , 20 (1): 29-39, DOI : 10.1016 / s0167-8396 (03) 00003-7
Cranston, M .; Hsu, P .; Марч П. (1989), "Гладкость выпуклой оболочки плоского броуновского движения", Annals of Probability , 17 (1): 144–150, JSTOR 2244202 , MR 0972777
Демейн, Эрик Д .; Гассенд, Блэз; О'Рурк, Джозеф ; Туссен, Годфрид Т. (2008), «Все многоугольники меняются до бесконечности ... верно?», Обзоры дискретной и вычислительной геометрии , Современная математика, 453 , Провиденс, Род-Айленд: Американское математическое общество, стр. 231–255, doi : 10.1090 / conm / 453/08801 , Руководство по ремонту 2405683
Dines, LL (1938), "О выпуклости", American Mathematical Monthly , 45 (4): 199-209, DOI : 10,2307 / 2302604 , JSTOR 2302604 , MR 1524247
Дирнбек, Ганс; Stachel, Hellmuth (1997), "Развитие олоида" (PDF) , Journal for Geometry and Graphics , 1 (2): 105–118, MR 1622664
Эдельсбруннер, Герберт ; Киркпатрик, Дэвид Г .; Сейдел, Раймунд (1983), "О форме множества точек на плоскости", IEEE Transactions по теории информации , 29 (4): 551-559, DOI : 10,1109 / TIT.1983.1056714
Эпштейн, администратор баз данных ; Марден А. (1987), «Выпуклые оболочки в гиперболическом пространстве, теорема Салливана и измеренные складчатые поверхности», в Эпштейне, DBA (редактор), Аналитические и геометрические аспекты гиперболического пространства (Ковентри / Дарем, 1984) , Серия лекций Лондонского математического общества, 111 , Кембридж: Cambridge University Press, стр. 113–253, MR 0903852
Эскобар, Лаура; Кавех, Киумарс (сентябрь 2020 г.), «Выпуклые многогранники, алгебраическая геометрия и комбинаторика» (PDF) , Уведомления Американского математического общества , 67 (8): 1116–1123
Гарднер, Л. Террелл (1984), "Элементарное доказательство теоремы Russo-Dye", Труды Американского математического общества , 90 (1): 171, DOI : 10,2307 / 2044692 , MR 0722439
Гельфанд И.М .; Капранов ММ ; Зелевинский, А. В. (1994), "6. многогранник Ньютона и Ие многогранники", дискриминанты, Результанты и многомерные детерминанты , Математика:. Теория и приложение, Birkhäuser, стр 193-213, DOI : 10.1007 / 978-0-8176-4771 -1 , ISBN 0-8176-3660-9, Руководство по ремонту 1264417
Getz, Wayne M .; Вилмерс, Кристофер К. (2004), «Локальная конструкция ближайшего соседа с выпуклой оболочкой домашних диапазонов и распределений использования» (PDF) , Ecography , Wiley, 27 (4): 489–505, doi : 10.1111 / j.0906 -7590.2004.03835.x
Грэм, Рональд Л .; Яо, Ф. Френсис (1983), "Нахождение выпуклой оболочки простого многоугольника", журнал алгоритмов , 4 (4): 324-331, DOI : 10,1016 / 0196-6774 (83) 90013-5 , MR 0729228
Грюнбаум, Бранко (2003), Выпуклые многогранники , Тексты для выпускников по математике, 221 (2-е изд.), Springer, ISBN 9780387004242
Gustin, Уильям (1947), «О внутренней части выпуклой оболочки множества евклидовой», Бюллетень Американского математического общества , 53 : 299-301, DOI : 10,1090 / S0002-9904-1947-08787-5 , MR 0020800
Харрис, Бернард (1971), «Математические модели для теории статистических решений» (PDF) , Оптимизационные методы в статистике (Proc. Sympos., Ohio State Univ., Columbus, Ohio, 1971) , стр. 369–389, MR 0356305
Герлих, Хорст (1992), "Гипервыпуклые оболочки метрических пространств", Труды симпозиума по общей топологии и приложениям (Оксфорд, 1989), Топология и ее приложения , 44 (1–3): 181–187, doi : 10.1016 / 0166-8641 (92) 90092-E , MR 1173256
Джонсон, Чарльз Р. (1976), "Нормальность и численный диапазон", Линейная алгебра и ее применения , 15 (1): 89-94, DOI : 10.1016 / 0024-3795 (76) 90080-х , МР 0460358
Кашивабара, Кендзи; Накамура, Масатака; Окамото, Иошио (2005), "аффинная теорема представления для абстрактных выпуклых геометрий", Вычислительная геометрия , 30 (2): 129-144, CiteSeerX 10.1.1.14.4965 , DOI : 10.1016 / j.comgeo.2004.05.001 , М.Р. 2107032
Като, Наоки (1992), "Проблемы оптимизации сети с двумя критериями", IEICE Trans. Основы электроники, связи и компьютерных наук , E75-A: 321–329
Кернохан, Брайан Дж .; Гитцен, Роберт А.; Миллспо, Джошуа Дж. (2001), «Анализ использования пространства и перемещений животных», Миллспо, Джошуа; Марзлафф, Джон М. (ред.), Радио слежение за популяциями животных , Academic Press, ISBN 9780080540221
Киркпатрик, К. (2006), "Теорема Шредингера HJW", Основы Physics Letters , 19 (1): 95-102, Arxiv : Квант-фот / 0305068 , DOI : 10.1007 / s10702-006-1852-1
Kiselman, Кристер О. (2002), "полугруппа операторов в теории выпуклости", Труды Американского математического общества , 354 (5): 2035-2053, DOI : 10,1090 / S0002-9947-02-02915-X , MR 1881029
Knuth, Donald E. (1992), Axioms and Hulls , Lecture Notes in Computer Science, 606 , Heidelberg: Springer-Verlag, DOI : 10.1007 / 3-540-55611-7 , ISBN 3-540-55611-7, Руководство по ремонту 1226891
Кениг, Денес (декабрь 1922 г.), «Über konvexe Körper», Mathematische Zeitschrift , 14 (1): 208–210, doi : 10.1007 / bf01215899; Смотри также обзор от Hans Радемахером (1922), СУЛ 48.0835.01
Крейн, Марк ; Милман, Дэвид (1940), "О крайних точках регулярных выпуклых множеств" , Studia Mathematica , 9 : 133–138
Крейн, М .; Шмулян В. (1940), "О правильно выпуклых множествах в пространстве, сопряженном с банаховым пространством", Annals of Mathematics , Second Series, 41 : 556–583, doi : 10.2307 / 1968735 , hdl : 10338.dmlcz / 100106 , JSTOR 1968735 , MR 0002009
Laurentini, А. (1994), "Визуальная концепция корпуса для силуэта на основе понимания изображений", IEEE Transactions на шаблон анализа и Machine Intelligence , 16 (2): 150-162, DOI : 10,1109 / 34,273735
Лэй, Стивен Р. (1982), Выпуклые множества и их приложения , John Wiley & Sons, ISBN 0-471-09584-2, Руководство по ремонту 0655598
Lee, DT (1983), "О нахождении выпуклой оболочки простого многоугольника", Международный журнал компьютерных и информационных наук , 12 (2): 87-98, DOI : 10.1007 / BF00993195 , MR 0724699
Мейсон, Герберт Б. (1908), Энциклопедия кораблей и судоходства , стр. 698
Маккаллум, Дункан; Avis, Дэвид (1979), "Линейный алгоритм для нахождения выпуклой оболочки простого многоугольника", Information Processing Letters , 9 (5): 201-206, DOI : 10,1016 / 0020-0190 (79) 90069-3 , MR 0552534
Ньютон, Исаак (24 октября 1676 г.), «Письмо Генри Ольденбургу» , проект Ньютона , Оксфордский университет
Nicola, Piercarlo (2000), "общего равновесия", Mainstream Математическая экономика в 20 - м веке , Springer, С. 197-215,. Дои : 10.1007 / 978-3-662-04238-0_16
Nilsen, Erlend B .; Педерсен, Симен; Линнелл, Джон округ Колумбия (2008), «Можно ли использовать дома с минимальным выпуклым полигоном для получения биологически значимых выводов?», Ecological Research , 23 (3): 635–639, doi : 10.1007 / s11284-007-0421-9
Оберман, Адам М. (2007), «Выпуклая оболочка - решение нелинейной проблемы препятствий», Труды Американского математического общества , 135 (6): 1689–1694, DOI : 10.1090 / S0002-9939-07-08887 -9 , Руководство по ремонту 2286077
Окна, Т. (2000), "Теория Шока в метрических пространствах", Zeitschrift für анализа унда Ihre Anwendungen , 19 (2): 303-314, DOI : 10,4171 / ZAA / 952 , МР 1768994
Ottmann, T .; Soisalon-Soininen, E .; Древесина, Дерик (1984), "Об определения и вычисления прямолинейных выпуклых оболочек", Информатика , 33 (3): 157-171, DOI : 10,1016 / 0020-0255 (84) 90025-2
Прасолов, Виктор В. (2004), «1.2.1 Теорема Гаусса – Лукаса» , Многочлены , алгоритмы и вычисления в математике, 11 , Springer, стр. 12–13, doi : 10.1007 / 978-3-642-03980- 5 , ISBN 3-540-40714-6, MR 2082772
Pulleyblank, WR (1983), «Многогранная комбинаторика», в Bachem, Achim; Корте, Бернхард; Grötschel, Мартин (ред.), Математическое программирование: современное состояние (XI в Международном симпозиуме по математическому программированию, Боннский 1982) , Springer, С. 312-345,. Дои : 10.1007 / 978-3-642-68874-4_13
Раппопорт, Ари (1992), «Эффективный адаптивный алгоритм для построения выпуклых разностей дерева простого многоугольника», компьютерная графика Форум , 11 (4): 235-240, DOI : 10.1111 / 1467-8659.1140235
Reay, Джон Р. (1979), "Несколько обобщения Тверберга", Израиль Журнал математики , 34 (3): 238-244 (1980), DOI : 10.1007 / BF02760885 , MR 0570883
Риффель, Элеонора Г .; Полак, Вольфганг Х. (2011), Квантовые вычисления: мягкое введение , MIT Press, стр. 215–216, ISBN 978-0-262-01506-6
Рокафеллар, Р. Тиррелл (1970), Выпуклый анализ , Princeton Mathematical Series, 28 , Princeton, NJ: Princeton University Press, MR 0274683
Росси, Hugo (1961), "Голоморфно выпуклых множеств в нескольких комплексных переменных", Анналы математики , второй серии, 74 : 470-493, DOI : 10,2307 / 1970292 , JSTOR 1970292 , MR 0133479
Rousseeuw, Peter J .; Рутс, Ида; Таки, John W. (1999), "О bagplot: двумерный boxplot", Американский Статистик , 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 , Кембридж: Издательство Кембриджского университета, DOI : 10.1017 / CBO9780511526282 , ISBN 0-521-35220-7, Руководство по ремонту 1216521
Ситон, Кэтрин А. (2017), «Сферироны и D-формы: связанная крючком связь», Journal of Mathematics and the Arts , 11 (4): 187–202, arXiv : 1603.08409 , doi : 10.1080 / 17513472.2017.1318512 , MR 3765242
Седых В. Д. Строение выпуклой оболочки пространственной кривой (1981), Труды семинара имени И. Г. Петровского, № 6, с. 239–256, MR 0630708., Переведенный в журнале советской математики 33 (4): 1140-1153, 1986, DOI : 10.1007 / BF01086114
Зонтаг, Эдуардо Д. (1982), «Замечания по кусочно-линейной алгебре» , Pacific Journal of Mathematics , 98 (1): 183–201, MR 0644949
Стейниц, Е. (1914), "Bedingt konvergente Reihen унд konvexe Systeme (Fortsetzung)", Журнал für умереть Reine унд Angewandte Mathematik , 144 : 1-40, DOI : 10.1515 / crll.1914.144.1 , MR 1580890
Талман, Луи А. (1977), "Неподвижные точки уплотняющих мультифункций в метрических пространствах с выпуклой структурой" , Kōdai Mathematical Seminar Reports , 29 (1-2): 62–70, MR 0463985
Туссен, Годфрид (1983), "Решение геометрических задач с помощью вращающихся суппортов", Труды IEEE MELECON '83, Афины , CiteSeerX 10.1.1.155.5671
Туссент, Годфрид (1986), «Оптимальный алгоритм для вычисления относительной выпуклой оболочки набора точек в многоугольнике», Труды EURASIP, Обработка сигналов III: Теории и приложения, Часть 2 , Северная Голландия, стр. 853– 856
Недели, Джеффри Р. (1993), "Выпуклые оболочки и изометрии cusped гиперболических 3-многообразий", Топология и ее приложения , 52 (2): 127-149, DOI : 10.1016 / 0166-8641 (93) 90032-9 , Руководство по ремонту 1241189
Вестерманн, LRJ (1976), "Об операторе корпуса", Indagationes Mathematicae , 38 (2): 179-184, DOI : 10,1016 / 1385-7258 (76) 90065-2 , МР 0404097
Уайт, Ф. Пурьер (апрель 1923 г.), «Чистая математика», Science Progress in the Twentieth Century , 17 (68): 517–526, JSTOR 43432008
Уитли, Роберт (1986), "Крейна-Шмульяна теорема", Труды Американского математического общества , 97 (2): 376-377, DOI : 10,2307 / 2046536 , MR 0835903
Уильямс, Джейсон; Россиньяк, Ярек (2005), «Затягивание: морфологическое упрощение, ограничивающее кривизну», в Kobbelt, Leif; Шапиро, Вадим (ред.), Материалы десятого симпозиума ACM по твердому и физическому моделированию 2005 г., Кембридж, Массачусетс, США, 13-15 июня 2005 г. , ACM, стр. 107–112, doi : 10.1145 / 1060244.1060257 , hdl : 1853/3736
Worton, Брюс Дж (1995), "Выпуклая оболочка на основе оценки размера домашнего расстояния", биометрии , 51 (4): 1206-1215, DOI : 10,2307 / 2533254 , JSTOR 2533254

Внешние ссылки [ править ]

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

"Выпуклая оболочка" , Математическая энциклопедия , EMS Press , 2001 [1994]
Вайсштейн, Эрик В. , «Выпуклый корпус» , MathWorld
"Выпуклые Халл" от Eric W. Weisstein , Wolfram Demonstrations Project 2007.

[FOOTNOTERockafellar197012-1] Рокафеллар (1970) , стр. 12.

[FOOTNOTEde_Bergvan_KreveldOvermarsSchwarzkopf20083-2] а б в де Берг и др. (2008) , стр. 3.

[3] Уильямс и Россиньяк (2005) . См. Также Дуглас Заре, ответ на «периметр невыпуклого множества» , MathOverflow , 16 мая 2014 г.

[FOOTNOTEOberman2007-4] Oberman (2007) .

[FOOTNOTEKnuth1992-5] Кнут (1992) .

[rock12lay17-6] Рокафеллар (1970) , стр. 12; Lay (1982) , стр. 17.

[7] де Берг и др. (2008) , стр. 6. Идея разделения корпуса на две цепи происходит от эффективного варианта Graham сканирования по Эндрю (1979) .

[FOOTNOTESontag1982-8] Зонтаг (1982) .

[FOOTNOTERockafellar197099-9] Рокафеллар (1970) , стр. 99.

[10] Стейниц (1914) ; Густин (1947) ; Барань, Качальски и Пах (1982)

[11] Grünbaum (2003) , стр. 16; Lay (1982) , стр. 21; Сакума (1977) .

[12] Этот пример приводится Талманом (1977) , замечание 2.6.

[FOOTNOTEWhitley1986-13] Уитли (1986) .

[14] Крейн и Милман (1940) ; Lay (1982) , стр. 43.

[FOOTNOTEOkon2000-15] Окна (2000) .

[FOOTNOTEKiselman2002-16] Kiselman (2002) .

[FOOTNOTEKashiwabaraNakamuraOkamoto2005-17] Kashiwabara, Nakamura & Okamoto (2005) .

[18] Крейна и Шмульяна (1940) , теорема 3, страницы 562-563; Шнайдер (1993) , теорема 1.1.2 (страницы 2–3) и глава 3.

[FOOTNOTEde_Bergvan_KreveldOvermarsSchwarzkopf2008254-19] де Берг и др. (2008) , стр. 254.

[FOOTNOTEGrünbaum200357-20] Grünbaum (2003) , стр. 57.

[FOOTNOTEde_Bergvan_KreveldOvermarsSchwarzkopf2008256-21] де Берг и др. (2008) , стр. 256.

[FOOTNOTEde_Bergvan_KreveldOvermarsSchwarzkopf2008245-22] де Берг и др. (2008) , стр. 245.

[FOOTNOTERappoport1992-23] Раппопорт (1992) .

[FOOTNOTEDemaineGassendO'RourkeToussaint2008-24] Demaine et al. (2008) .

[FOOTNOTECranstonHsuMarch1989-25] Крэнстон, Hsu & March (1989) .

[FOOTNOTESedykh1981-26] Седых (1981) .

[FOOTNOTEDirnböckStachel1997-27] Dirnböck & Stachel (1997) .

[FOOTNOTESeaton2017-28] Ситон (2017) .

[FOOTNOTERockafellar197036-29] Рокафеллар (1970) , стр. 36.

[FOOTNOTERockafellar1970149-30] Рокафеллар (1970) , стр. 149.

[FOOTNOTEAvisBremnerSeidel1997-31] Avis, Бремнер и Сайдел (1997) .

[FOOTNOTEde_Bergvan_KreveldOvermarsSchwarzkopf200813-32] де Берг и др. (2008) , стр. 13.

[33] Chazelle (1993) ; де Берг и др. (2008) , стр. 256.

[34] МакКаллум и Авис (1979) ; Грэм и Яо (1983) ; Ли (1983) .

[FOOTNOTEChan2012-35] Чан (2012) .

[FOOTNOTEBaschGuibasHershberger1999-36] Баш, Guibas & Хершбергер (1999) .

[FOOTNOTEToussaint1983-37] Перейти ↑ Toussaint (1983) .

[FOOTNOTEWestermann1976-38] Вестерманн (1976) .

[FOOTNOTELaurentini1994-39] Лаурентини (1994) .

[FOOTNOTEEdelsbrunnerKirkpatrickSeidel1983-40] а б Эдельсбруннер, Киркпатрик и Зайдель (1983) .

[FOOTNOTEToussaint1986-41] Перейти ↑ Toussaint (1986) .

[FOOTNOTEOttmannSoisalon-SoininenWood1984-42] Ottmann, Soisalon-Soininen & Wood (1984) .

[FOOTNOTEHerrlich1992-43] Herrlich (1992) .

[FOOTNOTERossi1961-44] Росси (1961) .

[FOOTNOTEBrown1979-45] Браун (1979) .

[FOOTNOTEChazelle1985-46] Chazelle (1985) .

[FOOTNOTEChangYap1986-47] Чанг и Яп (1986) .

[48] Артин (1967) ; Гельфанд, Капранов и Зелевинский (1994)

[FOOTNOTEPrasolov2004-49] Прасолов (2004) .

[FOOTNOTEJohnson1976-50] Джонсон (1976) .

[FOOTNOTEGardner1984-51] Гарднер (1984) .

[FOOTNOTEReay1979-52] Reay (1979) .

[FOOTNOTEEpsteinMarden1987-53] Эпштейн и Марден (1987) .

[FOOTNOTEWeeks1993-54] Недели (1993) .

[FOOTNOTERousseeuwRutsTukey1999-55] Rousseeuw, Колея и Тьюки (1999) .

[FOOTNOTEHarris1971-56] Харрис (1971) .

[57] Pulleyblank (1983) ; см. особенно замечания после теоремы 2.9.

[FOOTNOTEKatoh1992-58] Като (1992) .

[59] Никола (2000) . См., В частности, Раздел 16.9, Невыпуклость и приблизительное равновесие, стр. 209–210.

[FOOTNOTEChenWang2003-60] Чен и Ван (2003) .

[FOOTNOTEMason1908-61] Мейсон (1908) .

[62] Kernohan, Gitzen & Millspaugh (2001) , стр. 137–140; Нильсен, Педерсен и Линнелл (2008)

[FOOTNOTEWorton1995-63] Worton (1995) .

[FOOTNOTEGetzWilmers2004-64] Getz & Wilmers (2004) .

[FOOTNOTERieffelPolak2011-65] Риффель & Полак (2011) .

[FOOTNOTEKirkpatrick2006-66] Киркпатрик (2006) .

[67] Ньютон (1676) ; см. Auel (2019) , стр. 336, и Escobar & Kaveh (2020) .

[68] См., Например, White (1923) , стр. 520.

[FOOTNOTEDines1938-69] Dines (1938) .

vтеВыпуклый анализ и вариационный анализ
Темы (список)	Теория Шоке Выпуклая оптимизация Двойственность Множитель Лагранжа Превращение Лежандра Локально выпуклое топологическое векторное пространство Симплекс
Карты	Выпуклый конъюгат Вогнутый ( Закрыто K- Логарифмически Правильный Псевдо- Квази- ) Выпуклая функция Функция Invex Превращение Лежандра Полунепрерывность Субпроизводная
Основные результаты (список)	Теорема Фенхеля – Моро. Неравенство фенхеля-юнга Неравенство Дженсена Неравенство Эрмита – Адамара. Теорема Крейна – Мильмана. Лемма Мазура Робинсон-Урсеску Саймонс Урсеску
Наборы	Выпуклый корпус ( Псевдо ) Выпуклое множество Действующий домен Эпиграф Гипограф Зонотоп
Серии	Выпуклые ряды, связанные ( (cs, lcs) -замкнутые , (cs, bcs) -полные , (нижние) идеально выпуклые , (H x ) и (Hw x ) )