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

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

3-мерный выпуклый многогранник

Выпуклый многогранник является частным случаем многогранника , обладающим дополнительным свойством, что он также является выпуклым множеством, содержащимся в -мерном евклидовом пространстве . Большинство текстов ^{[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)-мерная грань ( нулевой многогранник ) каждого многогранника, является уникальным минимальным элементом решетки.

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

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

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

Выпуклый многогранник, как и любое компактное выпуклое подмножество R ⁿ , гомеоморфен замкнутому шару . ^[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. Ziegler, Günter M. (1995), Лекции по многогранникам , Graduate Texts in Mathematics, т. 152, Берлин, Нью-Йорк: Springer-Verlag.
3. Математическое программирование , Мелвин В. Джеттер (1986) ISBN 0-8247-7478-7 , стр. 68 
4. Hug, Daniel; Weil, Wolfgang (2020). Лекции по выпуклой геометрии . Выпускные тексты по математике. Cham, Швейцария: 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). «Конгруэнтные графы и связность графов». Amer. J. Math . 54 (1): 150–168. doi :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), «Простой способ отличить простой многогранник от его графа», Журнал комбинаторной теории , Сер. A, 49 (2): 381–383, doi : 10.1016/0097-3165(88)90064-7 , MR  0964396.
10. Kaibel, Volker; Schwartz, Alexander (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. doi :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. Bibcode :1991MaCom..57..259L. doi : 10.1090/S0025-5718-1991-1079024-2 . ISSN  0025-5718.

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

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