Выпуклая оболочка - Википедия - Convex hull

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

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

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

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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Функции

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

Вычисление

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

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

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

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

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

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

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

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

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

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

Приложения

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

Математика

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

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

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

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

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

Статистика

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

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

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

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

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

Экономика

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

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

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

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

Этология

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

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

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

История

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

Примечания

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

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

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