Выпуклый многогранник
Выпуклый многогранник является частным случаем многогранника , обладающим дополнительным свойством, заключающимся в том, что он также является выпуклым множеством, содержащимся в -мерном евклидовом пространстве . Большинство текстов [1] [2] используют термин «многогранник» для ограниченного выпуклого многогранника и слово «многогранник» для более общего, возможно, неограниченного объекта. Другие [3] (включая эту статью) допускают неограниченность многогранников. Термины «ограниченный/неограниченный выпуклый многогранник» будут использоваться ниже всякий раз, когда ограниченность критична для обсуждаемого вопроса. В других текстах выпуклый многогранник отождествляется с его границей.
Выпуклые многогранники играют важную роль как в различных разделах математики , так и в прикладных областях, особенно в линейном программировании .
Во влиятельных учебниках Грюнбаума [1] и Циглера [2] по этому предмету, а также во многих других текстах по дискретной геометрии выпуклые многогранники часто называют просто «многогранниками». Грюнбаум указывает, что это делается исключительно для того, чтобы избежать бесконечного повторения слова «выпуклый», и что обсуждение следует понимать как относящееся только к выпуклому многообразию (стр. 51).
Многогранник называется полномерным, если он является -мерным объектом в .
Выпуклый многогранник можно определить несколькими способами, в зависимости от того, что больше подходит для рассматриваемой задачи. Определение Грюнбаума дано в терминах выпуклого множества точек в пространстве. Другие важные определения: как пересечение полупространств ( представление полупространства) и как выпуклая оболочка множества точек (вершинное представление).
В своей книге « Выпуклые многогранники » Грюнбаум определяет выпуклый многогранник как компактное выпуклое множество с конечным числом крайних точек :
