Введение

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

Выпуклый политоп — это особый случай политопа, обладающий дополнительным свойством: он также является выпуклым множеством, содержащимся в -мерном евклидовом пространстве. Большинство текстов используют термин "политоп" для обозначения ограниченного выпуклого политопа, а слово "полиэдр" — для более общего, возможно, неограниченного объекта. Другие (включая эту статью) допускают, чтобы политопы были неограниченными. Термины "ограниченный/неограниченный выпуклый политоп" будут использоваться ниже, когда ограниченность критически важна для обсуждаемого вопроса. В некоторых текстах выпуклый политоп отождествляется с его границей. Выпуклые политопы играют важную роль как в различных областях математики, так и в прикладных областях, особенно в линейном программировании. В влиятельных учебниках Грунбаума, где — размерность пространства, содержащего рассматриваемый политоп. Следовательно, замкнутый выпуклый политоп можно рассматривать как множество решений системы линейных неравенств:

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

где — матрица размера , — столбец-вектор, координаты которого — переменные от до , а — столбец-вектор, координаты которого — правые части от до скалярных неравенств. Открытый выпуклый политоп определяется аналогичным образом, но в формулах вместо нестрогих используются строгие неравенства. Коэффициенты каждой строки матриц и соответствуют коэффициентам линейного неравенства, определяющего соответствующее полупространство. Таким образом, каждая строка матрицы соответствует поддерживающей гиперплоскости политопа — гиперплоскости, ограничивающей полупространство, содержащее политоп. Если поддерживающая гиперплоскость также пересекает политоп, она называется ограничивающей гиперплоскостью (поскольку, будучи поддерживающей гиперплоскостью, она может пересекать политоп только на границе политопа). Приведенное выше определение предполагает, что политоп является полноразмерным. В этом случае существует уникальный минимальный набор определяющих неравенств (с точностью до умножения на положительное число). Неравенства, принадлежащие этому уникальному минимальному набору, называются существенными. Множество точек политопа, удовлетворяющих существенному неравенству как равенству, называется гранью. Если политоп не является полноразмерным, то решения лежат в собственном аффинном подпространстве и политоп можно изучать как объект в этом подпространстве. В этом случае существуют линейные уравнения, которым удовлетворяют все точки политопа. Добавление одного из этих уравнений к любому из определяющих неравенств не изменяет политоп. Следовательно, в общем случае не существует уникального минимального набора неравенств, определяющих политоп. В общем случае пересечение произвольных полупространств не обязательно ограничено. Однако, если требуется определение, эквивалентное определению выпуклого корпуса, то ограниченность должна быть явно указана.

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

Требуя, чтобы пересечение полупространств приводило к ограниченному множеству, определение становится эквивалентным вершинному представлению. Приведем набросок доказательства того, что ограниченное пересечение полупространств приводит к политопу в вершинном представлении:

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

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

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

Два представления вместе обеспечивают эффективный способ определить, принадлежит ли данный вектор данному выпуклому политопу: чтобы доказать, что он находится в политопе, достаточно представить его в виде выпуклой комбинации вершин политопа (используется V-описание); чтобы доказать, что он не находится в политопе, достаточно представить одно определяющее неравенство, которое он нарушает. Тонкий момент в векторном представлении заключается в том, что количество векторов может быть экспоненциальным по отношению к размерности, поэтому доказательство принадлежности вектора политопу может быть экспоненциально длинным. К счастью, теорема Каратеодори гарантирует, что любой вектор в политопе может быть представлен не более чем d+1 определяющими векторами, где d – размерность пространства.

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

Для неограниченного политопа (иногда называемого полиэдром) H-описание остаётся справедливым, но V-описание требует расширения. Теодор Моцкин (1936) доказал, что любой неограниченный политоп можно представить как сумму ограниченного политопа и выпуклого многогранного конуса. Иными словами, любой вектор в неограниченном политопе является выпуклой комбинацией его вершин (его "определяющих точек") плюс конической комбинацией евклидовых векторов его бесконечных рёбер (его "определяющих лучей"). Это называется теоремой о конечном базисе. Решётка граней трёхмерного политопа определяется его графом. То же справедливо и для простых политопов произвольной размерности (Blind & Mani Levitska 1987, доказавшие гипотезу Михи Перлеса). Калай (1988) приводит простое доказательство, основанное на однозначных ориентациях стоков. Поскольку решётки граней этих политопов определяются их графами, задача определения комбинаторной изоморфности двух трёхмерных или простых выпуклых политопов может быть сформулирована эквивалентно как частный случай задачи изоморфизма графов. Однако эти задачи можно также рассмотреть в обратном порядке, показав, что проверка изоморфности политопов является задачей, полной с точки зрения изоморфизма графов.

Топологические свойства

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

Упрощенный разложение

Выпуклый политоп может быть разложен на симплициальный комплекс, или объединение симплексов, удовлетворяющий определенным свойствам. Для заданного выпуклого r-мерного политопа P, подмножество его вершин, содержащее (r+1) аффинно независимую точку, определяет r-симплекс. Возможно сформировать коллекцию подмножеств таким образом, чтобы объединение соответствующих симплексов было равно P, а пересечение любых двух симплексов было либо пустым, либо симплексом меньшей размерности. Это симплициальное разложение является основой многих методов вычисления объема выпуклого политопа, поскольку объем симплекса легко выражается формулой.

Конструкция представлений

Различные представления выпуклого политопа обладают разной полезностью, поэтому построение одного представления на основе другого является важной задачей. Задача построения V-представления известна как задача перечисления вершин, а задача построения H-представления – как задача перечисления граней. Хотя множество вершин ограниченного выпуклого политопа однозначно определяет его, во многих приложениях важно знать больше о комбинаторной структуре политопа, то есть о его решетке граней. Различные алгоритмы построения выпуклой оболочки решают как задачу перечисления граней, так и задачу построения решетки граней. В двумерном случае, то есть для выпуклого многоугольника, обе задачи – перечисления граней и вершин – сводятся к упорядочиванию вершин (соответственно, ребер) вокруг выпуклой оболочки. Это тривиальная задача, когда выпуклый многоугольник задан традиционным способом, то есть упорядоченной последовательностью его вершин. Если входной список вершин (или ребер) не упорядочен, временная сложность задач становится O(m log m). В алгебраической модели дерева решений вычислений известна соответствующая нижняя граница.

Вычисление объема

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