Выпуклый многогранник

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

Трехмерный выпуклый многогранник

Выпуклый многогранник — это частный случай многогранника , обладающий тем дополнительным свойством, что он также является выпуклым множеством, содержащимся в -мерном евклидовом пространстве . В большинстве текстов ^{[1] [2]} используется термин «многогранник» для обозначения ограниченного выпуклого многогранника и слово «многогранник» для более общего, возможно, неограниченного объекта. Другие ^[3] (включая эту статью) допускают неограниченность многогранников. Термины «ограниченный/неограниченный выпуклый многогранник» будут использоваться ниже всякий раз, когда ограниченность имеет решающее значение для обсуждаемого вопроса. Однако в других текстах выпуклый многогранник отождествляется с его границей. ${\displaystyle n}$ ${\displaystyle \mathbb {R} ^{n}}$

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

Во влиятельных учебниках Грюнбаума ^[1] и Циглера ^[2] по этому предмету, а также во многих других текстах по дискретной геометрии выпуклые многогранники часто называют просто «многогранниками». Грюнбаум указывает, что это делается исключительно для того, чтобы избежать бесконечного повторения слова «выпуклый» и что всю дискуссию следует понимать как применимую только к выпуклой разновидности (стр. 51).

Многогранник называется полномерным, если он является -мерным объектом в . ${\displaystyle n}$ ${\displaystyle \mathbb {R} ^{n}}$

Примеры

• Множество примеров ограниченных выпуклых многогранников можно найти в статье « Многогранник ».
• В двумерном случае полномерными примерами являются полуплоскость , полоса между двумя параллельными линиями, форма угла (пересечение двух непараллельных полуплоскостей), форма, определяемая выпуклой ломаной цепочкой с двумя лучи , прикрепленные к его концам, и выпуклый многоугольник .
• Частными случаями неограниченного выпуклого многогранника являются плита между двумя параллельными гиперплоскостями, клин, определяемый двумя непараллельными полупространствами , многогранный цилиндр (бесконечная призма ) и многогранный конус (бесконечный конус ), определяемый тремя или более полупространствами. пространства, проходящие через одну общую точку.

Определения

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

Представление вершин (выпуклая оболочка)

В своей книге «Выпуклые многогранники » Грюнбаум определяет выпуклый многогранник как компактное выпуклое множество с конечным числом крайних точек :

Множество выпукло , если для каждой пары различных точек в замкнутый отрезок с концами и содержится внутри . ${\displaystyle K}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle K}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle K}$

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

Пересечение полупространств

Выпуклый многогранник можно определить как пересечение конечного числа полупространств. Такое определение называется представлением полупространства ( H-представлением или H-описанием ). ^[1] Существует бесконечно много H-описаний выпуклого многогранника. Однако для полномерного выпуклого многогранника минимальное H-описание фактически уникально и задается набором полупространств, определяющих фасет . ^[1]

Замкнутое полупространство можно записать в виде линейного неравенства : ^[1]

${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}\leq b}$

где – размерность пространства, содержащего рассматриваемый многогранник. Следовательно, замкнутый выпуклый многогранник можно рассматривать как множество решений системы линейных неравенств : ${\displaystyle n}$

${\displaystyle {\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\cdots +\;&&a_{1n}x_{n}&&\;\leq \;&&&b_{1}\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\cdots +\;&&a_{2n}x_{n}&&\;\leq \;&&&b_{2}\\\vdots \;\;\;&&&&\vdots \;\;\;&&&&\vdots \;\;\;&&&&&\;\vdots \\a_{m1}x_{1}&&\;+\;&&a_{m2}x_{2}&&\;+\cdots +\;&&a_{mn}x_{n}&&\;\leq \;&&&b_{m}\\\end{alignedat}}}$

где – количество полупространств, определяющих многогранник. Кратко это можно записать как матричное неравенство: ${\displaystyle m}$

${\displaystyle Ax\leq b}$

где - матрица, - вектор-столбец, координаты которого являются переменными для и - вектор- столбец , координаты которого являются правыми частями скалярных неравенств. ${\displaystyle A}$ ${\displaystyle m\times n}$ ${\displaystyle x}$ ${\displaystyle n\times 1}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{n}}$ ${\displaystyle b}$ ${\displaystyle m\times 1}$ ${\displaystyle b_{1}}$ ${\displaystyle b_{m}}$

Открытый выпуклый многогранник определяется аналогично, с использованием в формулах строгих неравенств вместо нестрогих.

Коэффициенты каждой строки и соответствуют коэффициентам линейного неравенства, определяющего соответствующее полупространство. Следовательно, каждая строка в матрице соответствует опорной гиперплоскости многогранника, гиперплоскости, ограничивающей полупространство, содержащее многогранник. Если опорная гиперплоскость также пересекает многогранник, она называется ограничивающей гиперплоскостью (поскольку это опорная гиперплоскость, она может пересекать многогранник только на границе многогранника). ${\displaystyle A}$ ${\displaystyle b}$

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

Если многогранник не полномерен, то решения лежат в собственном аффинном подпространстве и многогранник можно изучать как объект в этом подпространстве. В этом случае существуют линейные уравнения, которым удовлетворяют все точки многогранника. Добавление одного из этих уравнений к любому из определяющих неравенств не меняет многогранник. Поэтому, вообще говоря, не существует единственного минимального набора неравенств, определяющих многогранник. ${\displaystyle Ax\leq b}$ ${\displaystyle \mathbb {R} ^{n}}$

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

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

Требуя, чтобы пересечение полупространств приводило к ограниченному множеству, определение становится эквивалентным представлению вершин. ^[4] Схема доказательства того, что ограниченное пересечение полупространств приводит к образованию многогранника в вершинном представлении, следующая:

Ограниченное пересечение замкнутых полупространств очевидно компактно и выпукло. Компактное и выпуклое множество с конечным числом крайних точек должно быть многогранником, где эти крайние точки образуют множество вершин. Осталось показать, что множество крайних точек (ограниченного пересечения конечного множества полупространств) также конечно: ${\displaystyle \mathbb {R} ^{n}}$

Пусть – крайняя точка , ограниченное пересечение замкнутых полупространств . Рассмотрим пересечение всех соответствующих гиперплоскостей (делящих пространство на полупространства), содержащих . Это дает аффинное подпространство . Для каждого полупространства, где гиперплоскость не содержит , мы рассматриваем пересечение внутренней части этих полупространств. Это дает открытое множество . Четко, . Так как является крайней точкой и относительно открыта , то отсюда следует, что должна быть 0-мерной и . Если бы оно не было 0-мерным, оно было бы внутренней точкой (по крайней мере) линии, что противоречит тому, чтобы быть крайней точкой. Поскольку каждая конструкция выбирает либо внутреннюю часть, либо границу одного из замкнутых полупространств, существует лишь конечное число различных множеств . Каждая крайняя точка принадлежит одному из этих множеств, а это значит, что количество крайних точек конечно. ${\displaystyle x\in {\textrm {ext}}(P)}$ ${\displaystyle P:=\bigcap _{i=1}^{k}H_{i}}$ ${\displaystyle H_{i}}$ ${\displaystyle x}$ ${\displaystyle U}$ ${\displaystyle x}$ ${\displaystyle O}$ ${\displaystyle x\in (U\cap O)\subseteq P}$ ${\displaystyle x}$ ${\displaystyle P}$ ${\displaystyle D:=U\cap O}$ ${\displaystyle D}$ ${\displaystyle D=\left\{x\right\}}$ ${\displaystyle D}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle D}$ ${\displaystyle k}$ ${\displaystyle D}$

Использование различных представлений

Два представления вместе обеспечивают эффективный способ решить, включен ли данный вектор в данный выпуклый многогранник: чтобы показать, что он находится в многограннике, достаточно представить его как выпуклую комбинацию вершин многогранника (V-описание используется); чтобы показать, что его нет в многограннике, достаточно привести одно определяющее неравенство, которое он нарушает. ^{[5] : 256}

Тонкий момент в представлении векторами заключается в том, что число векторов может быть экспоненциальным по размерности, поэтому доказательство того, что вектор находится в многограннике, может быть экспоненциально длинным. К счастью, теорема Каратеодори гарантирует, что каждый вектор в многограннике может быть представлен не более чем d +1 определяющими векторами, где d — размерность пространства.

Представление неограниченных многогранников

Для неограниченного многогранника (иногда называемого многогранником) H-описание по-прежнему справедливо, но V-описание должно быть расширено. Теодор Моцкин (1936) доказал, что любой неограниченный многогранник можно представить как сумму ограниченного многогранника и выпуклого многогранного конуса . ^[6] Другими словами, каждый вектор в неограниченном многограннике представляет собой выпуклую сумму его вершин («определяющих точек») плюс коническую сумму евклидовых векторов его бесконечных ребер («определяющих лучей»). Это называется теоремой о конечном базисе . ^[3]

Характеристики

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

Лицевая решетка

Гранью выпуклого многогранника называется любое пересечение многогранника с полупространством, при котором ни одна из внутренних точек многогранника не лежит на границе полупространства. Эквивалентно, грань — это набор точек, дающих равенство в некотором допустимом неравенстве многогранника. ^{[5] : 258}

Если многогранник d -мерен, его грани — это его ( d  − 1)-мерные грани, его вершины — это его 0-мерные грани, его ребра — это его 1-мерные грани, а его гребни — это его ( d  − 2)-мерные грани. объемные лица.

Учитывая выпуклый многогранник P , определенный матричным неравенством , если каждая строка в A соответствует ограничивающей гиперплоскости и линейно независима от других строк, то каждая грань P соответствует ровно одной строке A , и наоборот. Каждая точка на данной грани будет удовлетворять линейному равенству соответствующей строки матрицы. (Оно может удовлетворять или не удовлетворять равенству в других строках). Аналогично, каждая точка гребня будет удовлетворять равенству в двух строках A . ${\displaystyle Ax\leq b}$

Решетка граней квадратной пирамиды , изображенная в виде диаграммы Хассе ; каждая грань в решетке помечена своим набором вершин.

В общем случае ( n  −  j )-мерная грань удовлетворяет равенству в j конкретных строках A . Эти ряды составляют основу лица. С геометрической точки зрения это означает, что грань — это набор точек многогранника, лежащих в пересечении j ограничивающих многогранник гиперплоскостей.

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

Два многогранника называются комбинаторно изоморфными, если их решетки граней изоморфны .

Граф многогранника ( polytopalgraph , граф многогранника , 1-скелет ) — это набор только вершин и ребер многогранника, игнорируя многомерные грани. Например, многогранный граф — это многогранный граф трехмерного многогранника. По результату Уитни ^[7] решетка граней трехмерного многогранника определяется его графиком. То же самое верно и для простых многогранников произвольной размерности (Blind & Mani-Levitska 1987, доказывая гипотезу Миши Перлеса ). ^[8] Калай (1988) ^[9] дает простое доказательство, основанное на уникальных ориентациях стоков . Поскольку решетки граней этих многогранников определяются их графами, проблема определения того, являются ли два трехмерных или простых выпуклых многогранника комбинаторно изоморфными, может быть сформулирована эквивалентно как частный случай проблемы изоморфизма графов . Однако также возможно перевести эти проблемы в противоположном направлении, показав, что проверка изоморфизма многогранников является полной изоморфизмом графов. ^[10]

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

Выпуклый многогранник, как и любое компактное выпуклое подмножество ^в Rn , гомеоморфен замкнутому шару . ^[11] Пусть m обозначает размерность многогранника. Если многогранник полномерен, то m = n . Таким образом, выпуклый многогранник представляет собой m -мерное многообразие с краем, его эйлерова характеристика равна 1, а его фундаментальная группа тривиальна. Граница выпуклого многогранника гомеоморфна ( m  − 1)-сфере . Эйлерова характеристика границы равна 0 для четного m и 2 для нечетного m . Границу также можно рассматривать как мозаику ( m  − 1)-мерного сферического пространства , то есть как сферическую мозаику .

Симплициальное разложение

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

Для выпуклого r -мерного многогранника P подмножество его вершин, содержащее ( r +1) аффинно независимых точек, определяет r -симплекс . Можно сформировать набор подмножеств так, что объединение соответствующих симплексов равно P , а пересечение любых двух симплексов либо пусто, либо является симплексом меньшей размерности. Это симплициальное разложение лежит в основе многих методов вычисления объема выпуклого многогранника, поскольку объем симплекса легко задается формулой. ^[12]

Алгоритмические задачи для выпуклого многогранника

Строительство представительств

Разные представления выпуклого многогранника имеют разную полезность, поэтому построение одного представления по другому является важной проблемой. Проблема построения V-представления известна как проблема перечисления вершин , а проблема построения H-представления известна как проблема перечисления фасетов . Хотя множество вершин ограниченного выпуклого многогранника однозначно определяет его, в различных приложениях важно знать больше о комбинаторной структуре многогранника, т. е. о решетке его граней. Различные алгоритмы выпуклой оболочки занимаются как перебором граней, так и построением решетки граней.

В плоском случае, т. е. для выпуклого многоугольника , проблемы перечисления граней и вершин сводятся к упорядочиванию вершин (соответственно ребер) вокруг выпуклой оболочки. Это тривиальная задача, когда выпуклый многоугольник задается традиционным для многоугольников способом , т. е. упорядоченной последовательностью его вершин . Когда входной список вершин (или ребер) неупорядочен, временная сложность задач становится O ( m  log  m ). ^[13] Соответствующая нижняя граница известна в модели вычислений в виде алгебраического дерева решений . ^[14] ${\displaystyle v_{1},\dots ,v_{m}}$

Расчет объема

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

Смотрите также

• Ориентированный матроид
• Многогранник Нефа
• Теорема Стейница для выпуклых многогранников

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

1. Бранко Грюнбаум , Выпуклые многогранники , 2-е издание, подготовлено Фолькером Кайбелем, Виктором Клее и Гюнтером М. Циглером , 2003, ISBN  0-387-40409-0 , ISBN 978-0-387-40409-7 , 466 стр. 
2. Циглер, Гюнтер М. (1995), Лекции по многогранникам , Тексты для аспирантов по математике, том. 152, Берлин, Нью-Йорк: Springer-Verlag.
3. «Математическое программирование» , Мелвин В. Джетер (1986) ISBN 0-8247-7478-7 , стр. 68 
4. Обнимаю, Дэниел; Вайль, Вольфганг (2020). Лекции по выпуклой геометрии . Дипломные тексты по математике. Чам, Швейцария: Springer. стр. 30–35. ISBN 978-3-030-50180-8.
5. Ловаш, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1, МР  0859549
6. Моцкин, Теодор (1936). Beitrage zur Theorie der Linearen Ungleichungen (Докторская диссертация) . Иерусалим.{{cite book}}: CS1 maint: location missing publisher (link)
7. Уитни, Хасслер (1932). «Согласованные графы и связность графов». амер. Дж. Математика . 54 (1): 150–168. дои : 10.2307/2371086. hdl : 10338.dmlcz/101067 . JSTOR  2371086.
8. Слепой, Розвита ; Мани-Левитска, Питер (1987), «Загадки и изоморфизмы многогранников», Aequationes Mathematicae , 34 (2–3): 287–297, doi : 10.1007/BF01830678, MR  0921106, S2CID  120222616.
9. Калай, Гил (1988), «Простой способ отличить простой многогранник по его графику», Журнал комбинаторной теории , сер. А, 49 (2): 381–383, doi : 10.1016/0097-3165(88)90064-7 , МР  0964396.
10. Кайбель, Волкер; Шварц, Александр (2003). «О сложности проблем изоморфизма многогранников». Графы и комбинаторика . 19 (2): 215–230. arXiv : math/0106093 . doi : 10.1007/s00373-002-0503-y. S2CID  179936. Архивировано из оригинала 21 июля 2015 г.
11. Глен Э. Бредон , Топология и геометрия , 1993, ISBN 0-387-97926-3 , стр. 56. 
12. Бюлер, Б.; Энге, А.; Фукуда, К. (2000). «Точное вычисление объема многогранников: практическое исследование». Многогранники — Комбинаторика и вычисления . стр. 131–154. дои : 10.1007/978-3-0348-8438-9_6. ISBN 978-3-7643-6351-2.
13. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. «33.3 Нахождение выпуклой оболочки». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 947–957. ISBN 0-262-03293-7.
14. Яо, Эндрю Чи Чи (1981), «Нижняя граница поиска выпуклых оболочек», Журнал ACM , 28 (4): 780–787, doi : 10.1145/322276.322289 , MR  0677089, S2CID  13846330; Бен-Ор, Майкл (1983), «Нижние границы для деревьев алгебраических вычислений», Труды пятнадцатого ежегодного симпозиума ACM по теории вычислений (STOC '83) , стр. 80–86, doi : 10.1145/800061.808735.
15. Лоуренс, Джим (1991). «Вычисление объема многогранника». Математика вычислений . 57 (195): 259–271. Бибкод : 1991MaCom..57..259L. дои : 10.1090/S0025-5718-1991-1079024-2 . ISSN  0025-5718.

Внешние ссылки

• Вайсштейн, Эрик В. «Выпуклый многоугольник». Математический мир .
• Вайсштейн, Эрик В. «Выпуклый многогранник». Математический мир .
• Комей Фукуда , Часто задаваемые вопросы по многогранным вычислениям.