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

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

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

Определения

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

Связанные определения

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

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

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

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

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

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

Примеры

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

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

Свойства

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

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

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

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

Вариации и обобщения

• Правильный многогранник
• Ориентированный матроид
• Многогранник Нефа

См. также

• Алгоритм Чена

Ссылки

• Weisstein, Eric W. Convex polygon (англ.) на сайте Wolfram MathWorld.
• Weisstein, Eric W. Convex polyhedron (англ.) на сайте Wolfram MathWorld.
• Komei Fukuda, Polyhedral computation FAQ.