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

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

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

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

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

Примеры

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

Определения

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

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

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

Набор

K

из

\mathbb {R} ^{n}

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

a

,

b

в

K

, закрытый отрезок с концами

a

и

b

содержится внутри

K

.

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

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

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

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

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

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

{\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}}

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

Ax\leq b

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Граф многогранника ( polytopalgraph , граф многогранника , 1-скелет ) — это набор только вершин и ребер многогранника, игнорируя многомерные грани. Например, многогранный граф — это многогранный граф трехмерного многогранника. По результату Уитни ^[7] решетка граней трехмерного многогранника определяется его графиком. То же самое верно и для простых многогранников произвольной размерности (Blind & Mani-Levitska 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-представления известна как проблема перечисления фасетов . Хотя множество вершин ограниченного выпуклого многогранника однозначно определяет его, в различных приложениях важно больше знать о комбинаторной структуре многогранника, т. е. о решетке его граней. Различные алгоритмы выпуклой оболочки занимаются как перебором граней, так и построением решетки граней.

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

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

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

См. также

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

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г Бранко Грюнбаум , Выпуклые многогранники , 2-е издание, подготовлено Фолькером Кайбелем , Виктором Клее и Гюнтером М. Циглером , 2003 г., ISBN 0-387-40409-0 , ISBN 978-0-387-40409-7 , 466 стр.
^ Jump up to: ^а ^б Циглер, Гюнтер М. (1995), Лекции по многогранникам , Тексты для аспирантов по математике, том. 152, Берлин, Нью-Йорк: Springer-Verlag .
^ Jump up to: ^а ^б Математическое программирование Мелвина В. Джетера (1986). ISBN 0-8247-7478-7 , с. 68
^ Обнимаю, Дэниел; Вайль, Вольфганг (2020). Лекции по выпуклой геометрии . Дипломные тексты по математике. Чам, Швейцария: Springer. стр. 30–35. ISBN 978-3-030-50180-8 .
^ Jump up to: ^а ^б Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1 МР 0859549
^ Моцкин, Теодор (1936). Вклад в теорию линейных неравенств (кандидатская диссертация) . Иерусалим. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Уитни, Хасслер (1932). «Согласованные графы и связность графов». амер. Дж. Математика . 54 (1): 150–168. дои : 10.2307/2371086 . hdl : 10338.dmlcz/101067 . JSTOR 2371086 .
^ Слепой, Розвита ; Мани-Левитска, Питер (1987), «Загадки и изоморфизмы многогранников», Mathematical Equations , 34 (2–3): 287–297, doi : 10.1007/BF01830678 , MR 0921106 , S2CID 120222616 .
^ Калаи, Гил (1988), «Простой способ отличить простой многогранник по его графику», Журнал комбинаторной теории , сер. А, 49 (2): 381–383, doi : 10.1016/0097-3165(88)90064-7 , MR 0964396 .
^ Кайбель, Волкер; Шварц, Александр (2003). «О сложности проблем изоморфизма многогранников» . Графы и комбинаторика . 19 (2): 215–230. arXiv : math/0106093 . дои : 10.1007/s00373-002-0503-y . S2CID 179936 . Архивировано из оригинала 21 июля 2015 г.
^ Глен Э. Бредон , Топология и геометрия , 1993, ISBN 0-387-97926-3 , с. 56.
^ Бюлер, Б.; Энге, А.; Фукуда, К. (2000). «Точное вычисление объема многогранников: практическое исследование» . Многогранники — Комбинаторика и вычисления . стр. 131–154. дои : 10.1007/978-3-0348-8438-9_6 . ISBN 978-3-7643-6351-2 .
^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. «33.3 Нахождение выпуклой оболочки». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 947–957. ISBN 0-262-03293-7 .
^ Яо, Эндрю Чи Чи (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 .
^ Лоуренс, Джим (1991). «Вычисление объема многогранника» . Математика вычислений . 57 (195): 259–271. Бибкод : 1991MaCom..57..259L . дои : 10.1090/S0025-5718-1991-1079024-2 . ISSN 0025-5718 .

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

[grun-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г Бранко Грюнбаум , Выпуклые многогранники , 2-е издание, подготовлено Фолькером Кайбелем , Виктором Клее и Гюнтером М. Циглером , 2003 г., ISBN 0-387-40409-0 , ISBN 978-0-387-40409-7 , 466 стр.

[zieg-2] Jump up to: ^а ^б Циглер, Гюнтер М. (1995), Лекции по многогранникам , Тексты для аспирантов по математике, том. 152, Берлин, Нью-Йорк: Springer-Verlag .

[Jeter-3] Jump up to: ^а ^б Математическое программирование Мелвина В. Джетера (1986). ISBN 0-8247-7478-7 , с. 68

[4] Обнимаю, Дэниел; Вайль, Вольфганг (2020). Лекции по выпуклой геометрии . Дипломные тексты по математике. Чам, Швейцария: Springer. стр. 30–35. ISBN 978-3-030-50180-8 .

[lp-5] Jump up to: ^а ^б Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1 МР 0859549

[6] Моцкин, Теодор (1936). Вклад в теорию линейных неравенств (кандидатская диссертация) . Иерусалим. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[7] Уитни, Хасслер (1932). «Согласованные графы и связность графов». амер. Дж. Математика . 54 (1): 150–168. дои : 10.2307/2371086 . hdl : 10338.dmlcz/101067 . JSTOR 2371086 .

[8] Слепой, Розвита ; Мани-Левитска, Питер (1987), «Загадки и изоморфизмы многогранников», Mathematical Equations , 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 , MR 0964396 .

[10] Кайбель, Волкер; Шварц, Александр (2003). «О сложности проблем изоморфизма многогранников» . Графы и комбинаторика . 19 (2): 215–230. arXiv : math/0106093 . дои : 10.1007/s00373-002-0503-y . S2CID 179936 . Архивировано из оригинала 21 июля 2015 г.

[bredon-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 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]