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

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

Определения

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

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

Гранью выпуклого многогранника является пересечение многогранника полупространством, при котором никакая внутренняя точка многогранника не лежит на границе полупространства.
- 0-мерные грани называются вершинами,
- 1-мерные грани называются рёбрами.

n-мерный телесный многогранник называется простым, если в каждой его вершине сходится ровно n рёбер.
- Например, куб и додекаэдр являются простыми.

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

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

Задание многогранника через гиперплоскости граней называется H-представлением.
Задание многогранника как выпуклую оболочку его вершин называется V-представлением.

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

К выпуклым многогранникам относятся: платоновы тела, архимедовы многогранники, ромбические многогранники (ромбододекаэдр, ромботриаконтаэдр), многогранники Голдберга^[англ.]^[1].

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

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

Как показал Уитни^[3], решётка граней трёхмерного многогранника определяется его графом. То же самое верно, если многогранник является простым (Blind & Mani-Levitska (1987), в книге Kalai (1988) дано простое доказательство). Последний факт является инструментом в доказательстве, что с точки зрения вычислительной сложности задача определения, являются ли два выпуклых многогранника комбинаторно изоморфными, эквивалентна задаче определения, являются ли графы изоморфными, даже если ограничиться классами простых или симплексных многогранников.^[4]

Любой выпуклый многогранник допускает триангуляцию с множеством вершин совпадающим с множеством вершин многогранника.^[5]