Выпуклая оболочка
Наименьшее выпуклое множество, содержащее заданное множество

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

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

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

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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Конечные точечные множества

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

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

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

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

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

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

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

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

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

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

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

Функции

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

Вычисление

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

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

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

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

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

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

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

Приложения

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

Математика

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

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

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

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

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

Статистика

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

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

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

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

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

Экономика

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

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

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

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

Этология

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

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

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

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

Выпуклая оболочка соединений магния и углерода . [68] Ожидается, что Mg 2 C 3 будет нестабильным, поскольку он находится над нижней оболочкой.

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

История

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

Примечания

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

Ссылки

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