Наименьшее выпуклое множество, содержащее заданное множество
В геометрии выпуклая оболочка , выпуклая оболочка или выпуклое замыкание [1] формы — это наименьшее выпуклое множество , содержащее ее. Выпуклая оболочка может быть определена либо как пересечение всех выпуклых множеств, содержащих данное подмножество евклидова пространства , либо, что то же самое, как множество всех выпуклых комбинаций точек в подмножестве. Для ограниченного подмножества плоскости выпуклую оболочку можно представить как форму, заключенную в резиновую ленту, натянутую вокруг подмножества.
Выпуклые оболочки открытых множеств открыты, а выпуклые оболочки компактов компактны. Всякий выпуклый компакт есть выпуклая оболочка его крайних точек . Оператор выпуклой оболочки является примером оператора замыкания , и каждый антиматроид может быть представлен путем применения этого оператора замыкания к конечному набору точек. Алгоритмические проблемы поиска выпуклой оболочки конечного набора точек на плоскости или других евклидовых пространствах малой размерности, а также двойственная проблема пересечения полупространств являются фундаментальными проблемами вычислительной геометрии . Их можно решить за время для двух- или трехмерных наборов точек и за время, соответствующее сложности вывода в наихудшем случае, заданной теоремой о верхней границе в более высоких измерениях.
Множество точек евклидова пространства называется выпуклым, если оно содержит отрезки, соединяющие каждую пару его точек. Выпуклая оболочка данного множества может быть определена как [2]
Для ограниченных множеств на евклидовой плоскости, не всех на одной прямой, граница выпуклой оболочки представляет собой простую замкнутую кривую с минимальным периметром, содержащим . Можно представить, что вы растягиваете резиновую ленту так, чтобы она охватывала весь набор , а затем отпускаете ее, позволяя ей сжаться; когда он становится тугим, он охватывает выпуклую оболочку . [3] Эта формулировка не распространяется сразу на более высокие измерения: для конечного набора точек в трехмерном пространстве окрестность остовного дерева точек окружает их с сколь угодно малой площадью поверхности, меньшей, чем площадь поверхности выпуклого корпус. [4] Однако в более высоких измерениях варианты проблемы с препятствиями по поиску поверхности с минимальной энергией выше заданной формы могут иметь выпуклую оболочку в качестве решения. [5]
Для трехмерных объектов первое определение гласит, что выпуклая оболочка — это наименьший возможный выпуклый ограничивающий объем объектов. Определение, использующее пересечения выпуклых множеств, может быть расширено до неевклидовой геометрии , а определение, использующее выпуклые комбинации, может быть расширено от евклидовых пространств до произвольных вещественных векторных пространств или аффинных пространств ; Выпуклые оболочки также могут быть обобщены более абстрактным образом до ориентированных матроидов . [6]
Эквивалентность определений
Неочевидно, что первое определение имеет смысл: почему должно существовать единственное минимальное выпуклое множество, содержащее , для каждого ? Однако второе определение — пересечение всех выпуклых множеств, содержащих , — корректно определено. Это подмножество любого другого выпуклого множества , содержащего , потому что оно включено в число пересекающихся множеств. Таким образом, это в точности единственное минимальное выпуклое множество, содержащее . Следовательно, первые два определения эквивалентны. [2]
Каждое выпуклое множество, содержащее, должно (по предположению, что оно выпуклое) содержать все выпуклые комбинации точек из , поэтому множество всех выпуклых комбинаций содержится в пересечении всех выпуклых множеств, содержащих . И наоборот, множество всех выпуклых комбинаций само по себе является выпуклым множеством, содержащим , поэтому оно также содержит пересечение всех выпуклых множеств, содержащих , и, следовательно, второе и третье определения эквивалентны. [7]
Фактически, согласно теореме Каратеодори , если является подмножеством -мерного евклидова пространства, каждая выпуклая комбинация конечного числа точек из также является выпуклой комбинацией не более чем точек из . Множество выпуклых комбинаций набора точек является симплексом ; на плоскости это треугольник , а в трёхмерном пространстве — тетраэдр. Следовательно, каждая выпуклая комбинация точек принадлежит симплексу, вершины которого принадлежат , и третье и четвертое определения эквивалентны. [7]
Верхний и нижний корпуса
В двух измерениях выпуклая оболочка иногда делится на две части: верхнюю и нижнюю, простирающиеся между самой левой и самой правой точками корпуса. В более общем смысле, для выпуклых оболочек в любом измерении можно разделить границу оболочки на точки, обращенные вверх (точки, для которых восходящий луч не пересекается с оболочкой), точки, обращенные вниз, и крайние точки. Для трехмерных корпусов обращенные вверх и вниз части границы образуют топологические диски. [8]
Замкнутая выпуклая оболочка является пересечением всех замкнутых полупространств, содержащих . Если выпуклая оболочка сама по себе уже является замкнутым множеством (как это происходит, например, если — конечное множество или, в более общем случае, компактное множество ), то она равна замкнутой выпуклой оболочке. Однако пересечение замкнутых полупространств само по себе замкнуто, поэтому, когда выпуклая оболочка незамкнута, ее нельзя представить таким образом. [10]
Если открытая выпуклая оболочка множества -мерна , то каждая точка оболочки принадлежит открытой выпуклой оболочке не более чем точек из . Наборы вершин квадрата, правильного октаэдра или перекрестного многогранника более высокой размерности служат примерами, когда необходимы именно точки. [11]
Сохранение топологических свойств
Топологически выпуклая оболочка открытого множества сама по себе всегда открыта, а выпуклая оболочка компактного множества всегда сама компактна. Однако существуют замкнутые множества, у которых выпуклая оболочка не замкнута. [12] Например, замкнутое множество
Компактность выпуклых оболочек компактных множеств в конечномерных евклидовых пространствах обобщается теоремой Крейна–Смулиана , согласно которой замкнутая выпуклая оболочка слабо компактного подмножества банахова пространства (подмножества, компактного относительно слабого топология ) слабо компактна. [14]
Крайние точки
Крайняя точка выпуклого множества — это точка множества, которая не лежит ни на одном открытом отрезке между любыми двумя другими точками того же множества. Для выпуклой оболочки каждая крайняя точка должна входить в данное множество, так как в противном случае она не может образоваться как выпуклая комбинация данных точек. Согласно теореме Крейна-Милмана , каждый компактный выпуклый набор в евклидовом пространстве (или, в более общем смысле, в локально выпуклом топологическом векторном пространстве ) является выпуклой оболочкой его крайних точек. [15] Однако это может быть не так для выпуклых множеств, которые не являются компактными; например, вся евклидова плоскость и открытый единичный шар выпуклы, но ни одна из них не имеет крайних точек. Теория Шоке расширяет эту теорию от конечных выпуклых комбинаций крайних точек до бесконечных комбинаций (интегралов) в более общих пространствах. [16]
Геометрические и алгебраические свойства
Оператор закрытия
Оператор выпуклой оболочки обладает характерными свойствами оператора замыкания : [17]
Оно обширно , что означает, что выпуклая оболочка каждого множества является надмножеством .
Оно неубывает , что означает, что для каждых двух наборов и с выпуклая оболочка является подмножеством выпуклой оболочки .
Он идемпотентен , что означает, что для каждого выпуклая оболочка выпуклой оболочки такая же, как и выпуклая оболочка .
Применительно к конечному набору точек это оператор замыкания антиматроида , обстреливающий антиматроид множества точек. Таким образом, каждый антиматроид может быть представлен выпуклыми оболочками точек в евклидовом пространстве достаточно высокой размерности. [18]
сумма Минковского
Операции построения выпуклой оболочки и взятия суммы Минковского коммутируют друг с другом в том смысле, что сумма Минковского выпуклых оболочек множеств дает тот же результат, что и выпуклая оболочка суммы Минковского тех же множеств. Это делает шаг к теореме Шепли – Фолкмана, ограничивающей расстояние суммы Минковского от ее выпуклой оболочки. [19]
Проективная двойственность
Проективная двойственная операция построения выпуклой оболочки набора точек — это построение пересечения семейства замкнутых полупространств, все из которых содержат начало координат (или любую другую обозначенную точку). [20]
Особые случаи
Конечные множества точек
Выпуклая оболочка конечного множества точек образует выпуклый многоугольник, когда или, в более общем смысле, выпуклый многогранник в . Каждая крайняя точка оболочки называется вершиной и (по теореме Крейна-Милмана) каждый выпуклый многогранник является выпуклой оболочкой своих вершин. Это единственный выпуклый многогранник, вершины которого принадлежат и который охватывает все . [3]
Для множеств точек общего положения выпуклая оболочка является симплициальным многогранником . [21]
Согласно теореме о верхней границе , число граней выпуклой оболочки точек в -мерном евклидовом пространстве равно . [22] В частности, в двух и трех измерениях количество граней не более чем линейно по . [23]
Простые многоугольники
Выпуклая оболочка простого многоугольника охватывает данный многоугольник и разбивается им на области, одной из которых является сам многоугольник. Остальные области, ограниченные полигональной цепочкой многоугольника и одним выпуклым ребром оболочки, называются карманами . Рекурсивное вычисление одного и того же разложения для каждого кармана формирует иерархическое описание данного многоугольника, называемое его выпуклым деревом разностей . [24] Отражение кармана через выпуклый край его корпуса расширяет данный простой многоугольник в многоугольник с таким же периметром и большей площадью, и теорема Эрдеша-Надя утверждает, что этот процесс расширения в конечном итоге прекращается. [25]
Броуновское движение
Кривая, порожденная броуновским движением на плоскости, в любой фиксированный момент времени имеет вероятность 1 иметь выпуклую оболочку, граница которой образует непрерывно дифференцируемую кривую . Однако для любого угла в диапазоне будут моменты во время броуновского движения, когда движущаяся частица касается границы выпуклой оболочки в точке угла . Хаусдорфова размерность этого набора исключительных моментов равна (с высокой вероятностью) . [26]
Выпуклая оболочка или нижняя выпуклая оболочка функции в реальном векторном пространстве — это функция, надграфик которой является нижней выпуклой оболочкой надграфика функции . Это единственная максимальная выпуклая функция, мажорируемая . [30] Определение может быть распространено на выпуклую оболочку набора функций (полученную из выпуклой оболочки объединения их надграфиков или, что то же самое, из их поточечного минимума ) и в этой форме двойственно выпуклой сопряженной операции . [31]
Вычисление
В вычислительной геометрии известен ряд алгоритмов вычисления выпуклой оболочки для конечного набора точек и для других геометрических объектов. Вычисление выпуклой оболочки означает построение однозначного и эффективного представления требуемой выпуклой формы. Выходные представления, которые рассматривались для выпуклых оболочек множеств точек, включают список линейных неравенств , описывающих грани оболочки, неориентированный граф граней и их смежностей или полную решетку граней оболочки. [32] В двух измерениях, возможно, будет достаточно просто перечислить точки, являющиеся вершинами, в их циклическом порядке вокруг оболочки. [3]
Для выпуклых оболочек в двух или трех измерениях сложность соответствующих алгоритмов обычно оценивается через , количество входных точек, и , количество точек на выпуклой оболочке, которое может быть значительно меньше . Для корпусов более высоких размерностей в анализ также может включаться количество граней других измерений. Сканирование Грэма позволяет вычислить выпуклую оболочку точек плоскости во времени . Для точек в двух и трех измерениях известны более сложные алгоритмы, чувствительные к выходным данным , которые вычисляют выпуклую оболочку во времени . К ним относятся алгоритм Чана и алгоритм Киркпатрика-Зейделя . [33] Для размерностей время вычисления выпуклой оболочки равно , что соответствует выходной сложности задачи в наихудшем случае. [34] Выпуклая оболочка простого многоугольника на плоскости может быть построена за линейное время . [35]
Структуры данных динамической выпуклой оболочки могут использоваться для отслеживания выпуклой оболочки набора точек, в которых происходит вставка и удаление точек, [36] , а кинетические структуры выпуклой оболочки могут отслеживать выпуклую оболочку для точек, движущихся непрерывно. [37]
Построение выпуклых оболочек также служит инструментом, строительным блоком для ряда других вычислительно-геометрических алгоритмов, таких как метод вращающихся штангенциркулей для вычисления ширины и диаметра множества точек. [38]
Связанные структуры
Несколько других фигур могут быть определены из набора точек аналогично выпуклой оболочке, как минимальное надмножество с некоторым свойством, пересечение всех фигур, содержащих точки из данного семейства фигур, или объединение всех комбинаций фигур. очков за определенный тип комбинации. Например:
Аффинная оболочка — это наименьшее аффинное подпространство евклидова пространства, содержащее заданное множество или объединение всех аффинных комбинаций точек в множестве. [39]
Линейная оболочка — это наименьшее линейное подпространство векторного пространства, содержащее заданный набор, или объединение всех линейных комбинаций точек в наборе. [39]
Коническая оболочка или положительная оболочка подмножества векторного пространства — это набор всех положительных комбинаций точек в подмножестве. [39]
Визуальная оболочка трехмерного объекта по отношению к набору точек зрения состоит из таких точек, что каждый луч из точки обзора пересекает объект. Эквивалентно, это пересечение (невыпуклых) конусов, образуемых контуром объекта относительно каждой точки обзора. Он используется в 3D-реконструкции как самая большая форма, которая может иметь одинаковые очертания с заданных точек зрения. [40]
Круглая оболочка или альфа-оболочка подмножества плоскости — это пересечение всех дисков заданного радиуса, содержащих это подмножество. [41]
Относительная выпуклая оболочка подмножества двумерного простого многоугольника - это пересечение всех относительно выпуклых надмножеств, где множество внутри одного и того же многоугольника является относительно выпуклым, если оно содержит геодезическую между любыми двумя своими точками. [42]
Ортогональная выпуклая оболочка или прямолинейная выпуклая оболочка - это пересечение всех ортогонально выпуклых и связных надмножеств, где множество является ортогонально выпуклым, если оно содержит все отрезки, параллельные осям между парами его точек. [43]
Триангуляция Делоне множества точек и ее двойственная диаграмма Вороного математически связаны с выпуклыми оболочками: триангуляцию Делоне множества точек можно рассматривать как проекцию выпуклой оболочки в
[ 46 ]. Набор точек представляет собой вложенное семейство (невыпуклых) геометрических объектов, описывающих форму набора точек на разных уровнях детализации. Каждая форма альфа представляет собой объединение некоторых особенностей триангуляции Делоне, выбранных путем сравнения их радиуса описанной окружности с параметром альфа. Набор точек сам по себе образует одну конечную точку этого семейства фигур, а его выпуклая оболочка образует другую конечную точку. [41]
Выпуклые слои множества точек представляют собой вложенное семейство выпуклых многоугольников, самым внешним из которых является выпуклая оболочка, а внутренние слои создаются рекурсивно из точек, которые не являются вершинами выпуклой оболочки. [47]
Выпуклый череп многоугольника — это самый большой выпуклый многоугольник, содержащийся внутри него. Его можно найти за полиномиальное время , но показатель степени алгоритма высок. [48]
Многоугольники Ньютона одномерных многочленов и многогранники Ньютона многомерных многомерных полиномов представляют собой выпуклые оболочки точек, полученные из показателей степеней членов многочлена, и могут использоваться для анализа асимптотического поведения многочлена и оценок его корней. [49] Выпуклые оболочки и многочлены также объединяются в теореме Гаусса-Люкаса , согласно которой все корни производной многочлена лежат внутри выпуклой оболочки корней многочлена. [50]
Определения выпуклого множества как содержащего отрезки прямых между своими точками и выпуклой оболочки как пересечения всех выпуклых надмножеств применимы как к гиперболическим пространствам , так и к евклидовым пространствам. Однако в гиперболическом пространстве также можно рассматривать выпуклые оболочки множеств идеальных точек , точек, которые не принадлежат самому гиперболическому пространству, но лежат на границе модели этого пространства. Границы выпуклых оболочек идеальных точек трехмерного гиперболического пространства аналогичны линейчатым поверхностям в евклидовом пространстве, а их метрические свойства играют важную роль в гипотезе геометризации в низкомерной топологии . [54] Гиперболические выпуклые оболочки также использовались как часть расчета канонических триангуляций гиперболических многообразий и применялись для определения эквивалентности узлов . [55]
См. также раздел о броуновском движении для применения выпуклых оболочек к этому предмету и раздел о пространственных кривых для их применения к теории развертывающихся поверхностей .
Статистика
В робастной статистике выпуклая оболочка обеспечивает один из ключевых компонентов диаграммы мешков — метода визуализации распределения двумерных точек выборки. Контуры глубины Тьюки образуют вложенное семейство выпуклых множеств с выпуклой оболочкой, расположенной снаружи, а на диаграмме мешков также отображается еще один многоугольник из этого вложенного семейства, контур с глубиной 50%. [56]
В статистической теории принятия решений набор рисков рандомизированного правила принятия решений представляет собой выпуклую оболочку точек риска лежащих в его основе детерминированных правил принятия решений. [57]
Комбинаторная оптимизация
В комбинаторной оптимизации и полиэдральной комбинаторике центральными объектами исследования являются выпуклые оболочки индикаторных векторов решений комбинаторной задачи. Если можно найти грани этих многогранников, описывающие многогранники как пересечения полупространств, то для поиска оптимальных решений можно использовать алгоритмы, основанные на линейном программировании . [58] В многокритериальной оптимизации также используется другой тип выпуклой оболочки — выпуклая оболочка весовых векторов решений. Можно максимизировать любую квазивыпуклую комбинацию весов, находя и проверяя каждую вершину выпуклой оболочки, что часто более эффективно, чем проверка всех возможных решений. [59]
Экономика
В модели общего экономического равновесия Эрроу-Дебре предполагается, что агенты имеют выпуклые бюджетные множества и выпуклые предпочтения . Эти предположения о выпуклости в экономике можно использовать для доказательства существования равновесия. Когда фактические экономические данные невыпуклые , их можно сделать выпуклыми, взяв выпуклые оболочки. Теорему Шепли -Фолкмана можно использовать, чтобы показать, что для крупных рынков это приближение является точным и приводит к «квазиравновесию» для исходного невыпуклого рынка. [60]
Геометрическое моделирование
В геометрическом моделировании одним из ключевых свойств кривой Безье является то, что она лежит внутри выпуклой оболочки своих контрольных точек. Это так называемое «свойство выпуклой оболочки» можно использовать, например, для быстрого обнаружения пересечений этих кривых. [61]
В геометрии лодок и кораблей обхват цепи - это мера размера парусного судна, определяемая с помощью выпуклого поперечного сечения корпуса судна . Он отличается от обхвата обшивки периметром самого сечения, за исключением лодок и кораблей, имеющих выпуклый корпус. [62]
Этология
Выпуклая оболочка широко известна как минимальный выпуклый многоугольник в этологии , изучении поведения животных, где это классический, хотя, возможно, и упрощенный подход к оценке ареала обитания животного на основе точек, где животное наблюдалось. [63] Выбросы могут сделать минимальный выпуклый многоугольник чрезмерно большим, что мотивирует расслабленные подходы, содержащие только подмножество наблюдений, например, путем выбора одного из выпуклых слоев, который близок к целевому проценту выборок, [64 ] или в методе локальной выпуклой оболочки путем объединения выпуклых оболочек окрестностей точек. [65]
Квантовая физика
В квантовой физике пространство состояний любой квантовой системы — совокупность всех способов подготовки системы — представляет собой выпуклую оболочку, крайними точками которой являются положительно-полуопределенные операторы , известные как чистые состояния, а внутренние точки — смешанными состояниями. [66] Теорема Шредингера -ХЮВ доказывает, что любое смешанное состояние на самом деле можно записать как выпуклую комбинацию чистых состояний несколькими способами. [67]
Термодинамика
Выпуклая оболочка в термодинамике была обнаружена Джозайей Уиллардом Гиббсом (1873) [69] , хотя статья была опубликована до того, как выпуклая оболочка получила такое название. В наборе энергий материала нескольких стехиометрий стабильными будут только измерения на нижней выпуклой оболочке. При удалении точки из корпуса и последующем вычислении ее расстояния до корпуса расстояние до нового корпуса представляет собой степень стабильности фазы. [70]
История
Нижняя выпуклая оболочка точек на плоскости появляется в форме многоугольника Ньютона в письме Исаака Ньютона Генри Ольденбургу в 1676 году. [71] Сам термин «выпуклая оболочка» появляется еще в работах Гаррета Биркгофа. (1935), а соответствующий термин в немецком языке появляется раньше, например, в рецензии Ганса Радемахера на Кенига (1922). В этот период также использовались другие термины, такие как «выпуклая оболочка». [72] К 1938 году, по словам Ллойда Дайнса , термин «выпуклая оболочка» стал стандартным; Дайнс добавляет, что он считает этот термин неудачным, поскольку разговорное значение слова «корпус» предполагает, что оно относится к поверхности формы, тогда как выпуклая оболочка включает в себя внутреннюю часть, а не только поверхность. [73]
Примечания
^ Терминология «выпуклое замыкание» относится к тому факту, что выпуклая оболочка определяет оператор замыкания . Однако этот термин также часто используется для обозначения закрытой выпуклой оболочки , с которой его не следует путать — см., например, Fan (1959), стр. 48.
^ аб Рокафеллар (1970), с. 12.
^ abc де Берг и др. (2008), с. 3.
^ Уильямс и Россиньяк (2005). См. также Дуглас Зар, ответ на вопрос «периметр невыпуклого множества», MathOverflow , 16 мая 2014 г.
^ Оберман (2007).
^ Кнут (1992).
^ аб Рокафеллар (1970), с. 12; Лэй (1982), с. 17.
^ де Берг и др. (2008), с. 6. Идея разделения корпуса на две цепи исходит из эффективного варианта сканирования Грэма Эндрю (1979).
^ Зонтаг (1982).
^ Рокафеллар (1970), с. 99.
^ Стейниц (1914); Гастин (1947); Барань, Качальский и Пах (1982)
^ Грюнбаум (2003), с. 16; Лэй (1982), с. 21; Сакума (1977).
^ Этот пример приведен Талманом (1977), замечание 2.6.
^ Уитли (1986).
^ Керин и Милман (1940); Лэй (1982), с. 43.
^ Окон (2000).
^ Кисельман (2002).
^ Касивабара, Накамура и Окамото (2005).
^ Крейн и Шмулян (1940), Теорема 3, страницы 562–563; Шнайдер (1993), теорема 1.1.2 (стр. 2–3) и глава 3.
^ де Берг и др. (2008), с. 254.
^ Грюнбаум (2003), с. 57.
^ де Берг и др. (2008), с. 256.
^ де Берг и др. (2008), с. 245.
^ Раппопорт (1992).
^ Демейн и др. (2008).
^ Крэнстон, Сюй и Марч (1989).
^ Седых (1981).
^ Дирнбёк и Стачел (1997).
^ Ситон (2017).
^ Рокафеллар (1970), с. 36.
^ Рокафеллар (1970), с. 149.
^ Авис, Бремнер и Зайдель (1997).
^ де Берг и др. (2008), с. 13.
^ Шазель (1993); де Берг и др. (2008), с. 256.
^ МакКаллум и Авис (1979); Грэм и Яо (1983); Ли (1983).
^ Чан (2012).
^ Баш, Гибас и Хершбергер (1999).
^ Туссен (1983).
^ abc Вестерманн (1976).
^ Лаурентини (1994).
^ аб Эдельсбруннер, Киркпатрик и Зайдель (1983).
^ Туссен (1986).
^ Оттманн, Сойсалон-Сойнинен и Вуд (1984).
^ Херрлих (1992).
^ Росси (1961).
^ Браун (1979).
^ Шазель (1985).
^ Чанг и Яп (1986).
^ Артин (1967); Гельфанд, Капранов и Зелевинский (1994)
^ Прасолов (2004).
^ Джонсон (1976).
^ Гарднер (1984).
^ Рей (1979).
^ Эпштейн и Марден (1987).
^ Уикс (1993).
^ Руссиу, Рутс и Тьюки (1999).
^ Харрис (1971).
^ Пулибланк (1983); см. особенно замечания после теоремы 2.9.
^ Като (1992).
^ Никола (2000). См., в частности, раздел 16.9, Невыпуклость и приближенное равновесие, стр. 209–210.
^ Чен и Ван (2003).
^ Мейсон (1908).
^ Кернохан, Гитцен и Миллспо (2001), стр. 137–140; Нильсен, Педерсен и Линнелл (2008)
^ Уортон (1995).
^ Гетц и Уилмерс (2004).
^ Риффель и Полак (2011).
^ Киркпатрик (2006).
^ Ким и др. (2019).
^ Гиббс (1873).
^ Отье (2014); Фульц (2020)
^ Ньютон (1676); см. Ауэль (2019), стр. 336, и Эскобар и Каве (2020).
^ См., например, White (1923), стр. 520.
^ Дайнс (1938).
Рекомендации
Фан, Кай (1959), Выпуклые множества и их приложения. Летние лекции 1959 г., Аргонская национальная лаборатория.
Эндрю, AM (1979), «Еще один эффективный алгоритм для выпуклых оболочек в двух измерениях», Information Processing Letters , 9 (5): 216–219, doi : 10.1016/0020-0190(79)90072-3
Артин, Эмиль (1967), «2.5. Многоугольник Ньютона», Алгебраические числа и алгебраические функции , Гордон и Брич, стр. 37–43, MR 0237460
Чанг, Дж. С.; Яп, К.-К. (1986), «Полиномиальное решение задачи чистки картофеля», Дискретная и вычислительная геометрия , 1 (2): 155–182, doi : 10.1007/BF02187692 , MR 0834056
Эпштейн, администратор баз данных ; Марден, А. (1987), «Выпуклые оболочки в гиперболическом пространстве, теорема Салливана и измеренные складчатые поверхности», в Эпштейне, DBA (редактор), Аналитические и геометрические аспекты гиперболического пространства (Ковентри / Дарем, 1984) , Серия лекций Лондонского математического общества, том. 111, Кембридж: Издательство Кембриджского университета, стр. 113–253, MR 0903852.
Эскобар, Лаура; Каве, Киумарс (сентябрь 2020 г.), «Выпуклые многогранники, алгебраическая геометрия и комбинаторика» (PDF) , Уведомления Американского математического общества , 67 (8): 1116–1123, doi : 10.1090/noti2137, S2CID 221659506
Фульц, Брент (апрель 2020 г.), Фазовые переходы в материалах, Cambridge University Press, стр. 55, номер домена : 10.1017/9781108641449, ISBN 9781108641449
Гельфанд, И.М. ; Капранов М.М. ; Зелевинский, А. В. (1994), «6. Многогранники Ньютона и многогранники Чоу», Дискриминанты, результанты и многомерные определители , Математика: теория и приложения, Биркхойзер, стр. 193–213, doi : 10.1007/978-0-8176-4771 -1, ISBN 0-8176-3660-9, МР 1264417
Гетц, Уэйн М.; Уилмерс, Кристофер К. (2004), «Локальная конструкция выпуклой оболочки методом ближайшего соседа для домашних диапазонов и распределений использования» (PDF) , Ecography , Wiley, 27 (4): 489–505, doi : 10.1111/j.0906 -7590.2004.03835.x, S2CID 14592779
Гиббс, Уиллард Дж. (1873), «Метод геометрического представления термодинамических свойств веществ с помощью поверхностей», Труды Академии искусств и наук Коннектикута , 2 : 382–404.; перепечатано в «Научных статьях Дж. Уилларда Гиббса», Vol. I: Термодинамика , Longmans, Green, & Co., 1906, стр. 33–54.
Харрис, Бернард (1971), «Математические модели для статистической теории принятия решений» (PDF) , Методы оптимизации в статистике (Proc. Sympos., Университет штата Огайо, Колумбус, Огайо, 1971) , стр. 369–389, MR 0356305
Отье, Жоффруа (2014), «Подходы к интеллектуальному анализу данных для высокопроизводительного прогнозирования кристаллической структуры и соединений», в Атахан-Эвренк, Суле; Аспуру-Гузик, Алан (ред.), Прогнозирование и расчет кристаллических структур: методы и приложения , Темы современной химии, том. 345, Springer International Publishing, стр. 139–179, номер документа : 10.1007/128_2013_486, PMID 24287952.; см. стр. 143
Херрлих, Хорст (1992), «Гипервыпуклые оболочки метрических пространств», Труды симпозиума по общей топологии и приложениям (Оксфорд, 1989), Топология и ее приложения , 44 (1–3): 181–187, doi : 10.1016/ 0166-8641(92)90092-Е , МР 1173256
Като, Наоки (1992), «Проблемы оптимизации сети по бикритериям», IEICE Trans. Основы электроники, связи и информатики , E75-A: 321–329.
Кернохан, Брайан Дж.; Гитцен, Роберт А.; Миллспо, Джошуа Дж. (2001), «Анализ использования пространства и перемещений животных», в Миллспо, Джошуа; Марзлафф, Джон М. (ред.), Радиослежение и популяции животных , Academic Press, ISBN 9780080540221
Кисельман, Кристер О. (2002), «Полугруппа операторов в теории выпуклости», Труды Американского математического общества , 354 (5): 2035–2053, doi : 10.1090/S0002-9947-02-02915-X , MR 1881029
Кнут, Дональд Э. (1992), Аксиомы и оболочки, Конспекты лекций по информатике, том. 606, Гейдельберг: Springer-Verlag, номер документа : 10.1007/3-540-55611-7, ISBN 3-540-55611-7, MR 1226891, S2CID 5452191, заархивировано из оригинала 20 июня 2017 г. , получено 15 сентября 2011 г.
Крейн, М .; Шмулян, В. (1940), «О правильно выпуклых множествах в пространстве, сопряженном с банаховым пространством», Annals of Mathematics , Second Series, 41 (3): 556–583, doi : 10.2307/1968735, hdl : 10338.dmlcz /100106 , JSTOR 1968735, MR 0002009
Лаурентини, А. (1994), «Концепция визуальной оболочки для понимания изображений на основе силуэтов», IEEE Transactions on Pattern Analysis and Machine Intelligence , 16 (2): 150–162, doi : 10.1109/34.273735
Лэй, Стивен Р. (1982), Выпуклые множества и их приложения , John Wiley & Sons, ISBN 0-471-09584-2, МР 0655598
Ли, Д.Т. (1983), «О поиске выпуклой оболочки простого многоугольника», Международный журнал компьютерных и информационных наук , 12 (2): 87–98, doi : 10.1007/BF00993195, MR 0724699, S2CID 28600832
Мейсон, Герберт Б. (1908), Энциклопедия кораблей и судоходства, стр. 698
МакКаллум, Дункан; Авис, Дэвид (1979), «Линейный алгоритм поиска выпуклой оболочки простого многоугольника», Information Processing Letters , 9 (5): 201–206, doi : 10.1016/0020-0190(79)90069-3, MR 0552534
Ньютон, Исаак (24 октября 1676 г.), «Письмо Генри Ольденбургу», Проект Ньютона , Оксфордский университет.
Никола, Пьеркарло (2000), «Общее конкурентное равновесие», Основная математическая экономика в 20 веке , Springer, стр. 197–215, doi : 10.1007/978-3-662-04238-0_16
Нильсен, Эрленд Б.; Педерсен, Симен; Линнелл, Джон, округ Колумбия (2008), «Можно ли использовать минимальные диапазоны домов выпуклых многоугольников для получения биологически значимых выводов?», Ecoological Research , 23 (3): 635–639, Bibcode : 2008EcoR...23..635N, doi : 10.1007/s11284-007-0421-9, S2CID 30843551
Оберман, Адам М. (2007), «Выпуклая оболочка — это решение нелинейной проблемы с препятствиями», Proceedings of the American Mathematical Society , 135 (6): 1689–1694, doi : 10.1090/S0002-9939-07-08887 -9 , МР 2286077
Окон, Т. (2000), «Теория Шоке в метрических пространствах», 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, номер документа : 10.1007/978-3-642-03980-5, ISBN.3-540-40714-6, МР 2082772
Пуллибланк, WR (1983), «Многогранная комбинаторика», в Бачеме, Ахиме; Корте, Бернхард; Гретшель, Мартин (ред.), Математическое программирование: современное состояние (XI-й Международный симпозиум по математическому программированию, Бонн, 1982 г.) , Springer, стр. 312–345, doi : 10.1007/978-3-642-68874-4_13
Раппопорт, Ари (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
Рокафеллар, Р. Тиррелл (1970), Выпуклый анализ , Princeton Mathematical Series, vol. 28, Принстон, Нью-Джерси: Издательство Принстонского университета, MR 0274683
Росси, Хьюго (1961), «Голоморфно выпуклые множества с несколькими комплексными переменными», Annals of Mathematics , Second Series, 74 (3): 470–493, doi : 10.2307/1970292, JSTOR 1970292, MR 0133479
Сакума, Ицуо (1977), «Замкнутость выпуклых оболочек», Журнал экономической теории , 14 (1): 223–227, doi : 10.1016/0022-0531(77)90095-3
Шнайдер, Рольф (1993), Выпуклые тела: теория Брунна-Минковского, Энциклопедия математики и ее приложений, том. 44, Кембридж: Издательство Кембриджского университета, номер документа : 10.1017/CBO9780511526282, ISBN.0-521-35220-7, МР 1216521
Ситон, Кэтрин А. (2017), «Сфериконы и D-формы: связанная крючком связь», Журнал математики и искусств , 11 (4): 187–202, arXiv : 1603.08409 , doi : 10.1080/17513472.2017.1318512, MR 3765242, S2CID 84179479
Седых, В.Д. (1981), "Строение выпуклой оболочки пространственной кривой", Труды семинара имени И.Г. Петровского (6): 239–256, МР 0630708, переведено в Журнал советской математики 33 (4): 1140–1153, 1986, doi : 10.1007/BF01086114.
Талман, Луи А. (1977), «Неподвижные точки для уплотнения мультифункций в метрических пространствах с выпуклой структурой», Отчеты математического семинара Кодай , 29 (1–2): 62–70, MR 0463985
Туссен, Годфрид (1983), «Решение геометрических задач с помощью вращающихся штангенциркулей», Труды IEEE MELECON '83, Афины , CiteSeerX 10.1.1.155.5671
Туссен, Годфрид (1986), «Оптимальный алгоритм вычисления относительной выпуклой оболочки набора точек многоугольника», Труды EURASIP, Обработка сигналов III: Теории и приложения, Часть 2 , Северная Голландия, стр. 853– 856
Уикс, Джеффри Р. (1993), «Выпуклые оболочки и изометрии гиперболических трехмерных многообразий с точками возврата», Топология и ее приложения , 52 (2): 127–149, doi : 10.1016/0166-8641(93)90032-9 , МР 1241189
Уильямс, Джейсон; Россиньяк, Ярек (2005), «Затягивание: морфологическое упрощение, ограничивающее кривизну», в Коббелте, Лейф; Шапиро, Вадим (ред.), Труды десятого симпозиума ACM по твердотельному и физическому моделированию, 2005 г., Кембридж, Массачусетс, США, 13–15 июня 2005 г., ACM, стр. 107–112, doi : 10.1145/1060244.1060257, hdl : 1853/3736, S2CID 15514388
Уортон, Брюс Дж. (1995), «Оценщик размера домашнего диапазона на основе выпуклой оболочки», Biometrics , 51 (4): 1206–1215, doi : 10.2307/2533254, JSTOR 2533254
Внешние ссылки
В Викибуке «Реализация алгоритма» есть страница на тему: Выпуклая оболочка.