Выпуклый многогранник - NiNa.Az

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

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

Определения

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

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

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

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

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

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

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

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

Примеры

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

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

Свойства

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

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

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

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

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

• Правильный многогранник
• Ориентированный матроид
• ^[англ.]

См. также

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

Примечания

1. https://scientificrussia.ru/articles/new-class-of-polyhedra-discovered Архивная копия от 11 февраля 2017 на Wayback Machine Новый класс геометрических фигур назвали многранником Голдберга
2. ^[англ.]. Topology and Geometry. — 1993. — ISBN 0-387-97926-3, p. 56..
3. Hassler Whitney. Congruent graphs and the connectivity of graphs // Amer. J. Math.. — 1932. — Т. 54, вып. 1. — С. 150–168. — JSTOR 2371086.
4. Volker Kaibel, Alexander Schwartz. {{{заглавие}}} // Graphs and Combinatorics. — 2003. — Т. 19, вып. 2. — С. 215–230. Архивировано 21 июля 2015 года.
5. B. Büeler, A. Enge, K. Fukuda. Exact Volume Computation for Polytopes: A Practical Study. Polytopes — Combinatorics and Computation.. — 2000. — С. 131. — ISBN 978-3-7643-6351-2. — doi:10.1007/978-3-0348-8438-9_6..

Ссылки

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