N-мерный многогранник

n - мерный многогранник — это геометрический объект, который обобщает трехмерный многогранник на n -мерное пространство. Он определяется как набор точек реального аффинного (или евклидова ) пространства любой размерности n , имеющего плоские стороны. Альтернативно его можно определить как пересечение конечного числа полупространств . В отличие от трехмерного многогранника он может быть ограниченным или неограниченным. В этой терминологии ограниченный многогранник называется многогранником . ^[1]^[2]

Аналитически выпуклый многогранник выражается как множество решений системы линейных неравенств a _i^Тx ≤ b _i , где a _i — векторы из R ^н и b _я скаляры. Это определение многогранников особенно важно, поскольку оно обеспечивает геометрическую перспективу проблем линейного программирования . ^[3]^: 9

Примеры

Многие традиционные многогранные формы представляют собой n-мерные многогранники. Другие примеры включают в себя:

Полупространство — это многогранник , определяемый одним линейным неравенством 1 _,^ТИкс ≤ б ₁ .
Гиперплоскость — это многогранник, определяемый двумя неравенствами: a ₁^Тх ≤ b ₁ и а ₁^Тx ≥ b ₁ (что эквивалентно -a ₁^Тх ≤ - б ₁ ).
Квадрант на плоскости. Например, область декартовой плоскости, состоящая из всех точек выше горизонтальной оси и справа от вертикальной оси: ${ (x, y) : x \geq 0, y \geq 0$ }. Его стороны - это две положительные оси, в остальном он неограничен.
Октант в евклидовом 3-мерном пространстве, ${ (x, y, z) : x \geq 0, y \geq 0, z \geq 0$ }.
Призма бесконечной протяженности. Например, вдвойне бесконечная квадратная призма в 3-мерном пространстве, состоящая из квадрата в плоскости xy , протянутого вдоль оси z : ${ (x, y, z) : 0 \leq x \leq 1, 0 \leq y \leq 1$ }.
Каждая ячейка мозаики Вороного представляет собой многогранник. мозаике Вороного множества S ячейка A , соответствующая точке $c \in S$ ограничена (следовательно, традиционный многогранник), когда c лежит внутри , выпуклой оболочки S В , и в противном случае (когда c на границе лежит выпуклая оболочка S ) A неограничена.

Грани и вершины

Подмножество F многогранника P называется гранью P , если существует полупространство H (определяемое некоторым неравенством a ₁^Тx ≤ b ₁ ) такой, что содержит P и F является пересечением H и P. H ^[3]^: 9

грань содержит одну точку { } , то v называется вершиной P. v Если
Если грань F непуста и - 1 мерна, то F называется фасетой P n .

Предположим, P — многогранник, определенный Ax ≤ b , где A имеет полный ранг столбца. Тогда v является вершиной P тогда и только тогда, когда v является базовым допустимым решением линейной системы Ax ⩽ b . ^[3]^: 10

Стандартное представление

Представление многогранника набором линейных неравенств не однозначно. Обычно определяют стандартное представление для каждого многогранника P : ^[3]^: 9

Если P полномерен, то его стандартное представление представляет собой набор неравенств такой, что каждое неравенство a _i^Тx ≤ b _i определяет ровно одну грань P , и, более того, неравенства нормализованы так, что $\|a_{i}\|_{\infty }=1$ для всех я .
Если P не полномерен, то он содержится в своей аффинной оболочке , которая определяется набором линейных уравнений C x= d . Можно выбрать C так, что C = ( I , C '), где I — единичная матрица . Стандартное представление P содержит этот набор C x= d и набор неравенств такой, что каждое неравенство a _i^Тx ≤ b _i определяет ровно одну грань P , неравенства нормализованы так, что $\|a_{i}\|_{\infty }=1$ для всех i , и каждый a _i ортогонален каждой C. строке Это представление уникально с точностью до выбора столбцов единичной матрицы.

Представление конусами и выпуклыми оболочками

Если P — многогранник (ограниченный многогранник), то его можно представить множеством вершин V , поскольку P — это просто выпуклая оболочка V : P = conv( V ).

Если P — общий (возможно, неограниченный) многогранник, то его можно представить в виде: P = conv(V) + cone(E), где V — (как и раньше) множество вершин P , а E — еще одно конечное множество. , а конус обозначает коническую оболочку . Установленный конус (E) также называется спада конусом P . ^[3]^: 10

Теорема Каратеодори утверждает, что если P - d -мерный многогранник, то каждую точку в P можно записать как выпуклую комбинацию не более d +1 аффинно независимых вершин P . Теорему можно обобщить: если P — любой d -мерный многогранник, то каждую точку в P можно записать в виде выпуклой комбинации точек v ₁ ,..., v _s , v ₁ + e ₁ ,..., v ₁ + e _t с s + t ⩽ d +1, такие, что v ₁ ,..., v _s — элементы минимальных непустых граней P , а e ₁ ,..., e _t — элементы минимальных ненулевых граней P конус рецессии P . ^[3]^: 10

Сложность представления

При решении алгоритмических задач на многогранниках важно знать, можно ли представить определенный многогранник кодировкой с малым числом бит. Существует несколько мер сложности представления многогранника P : ^[3]^: 163

P имеет фасетную сложность не более f , если P может быть представлен системой линейных неравенств с рациональными коэффициентами, такой, что длина кодирования каждого неравенства (т. е. длина двоичного кодирования всех рациональных чисел, появляющихся в качестве коэффициентов в неравенстве) равна максимум ф . Заметим, что f ≥ n +1, так как в каждом неравенстве n+1 коэффициентов.
P имеет вершинную сложность не более v , если P можно представить как conv( V )+cone( E ), где V и E - конечные множества, такие, что каждая точка в V или E имеет длину кодирования не более v . Обратите внимание, что v ≥ n , поскольку n коэффициентов. в каждом векторе

Эти два вида сложности тесно связаны между собой: ^[3]^{: Лем.6.2.4}

Если P имеет фасетную сложность не более f , то P имеет вершинную сложность не более 4 n ² ф .
Если P имеет сложность вершин не более v , то P имеет сложность фасет не более 3 n ² v .

Многогранник P называется хорошо описанным , если известны n (количество измерений) и f (верхняя граница сложности грани). Это эквивалентно требованию, чтобы мы знали n и v (верхняя граница сложности вершины).

В некоторых случаях мы знаем верхнюю границу сложности грани многогранника P , но не знаем конкретных неравенств, которые достигают этой верхней границы. Однако можно доказать, что длина кодирования в любом стандартном представлении P не превышает 35 n. ² ф . ^[3]^{: Лем.6.2.3}

Сложность представления P подразумевает верхнюю и нижнюю границы объема P : ^[3]^: 165

Если сложность вершин P не превышает v , то тривиально все вершины P содержатся в шаре радиуса 2. ^v вокруг начала. Это означает, что если P — многогранник, то сам P описан в этом шаре.
Если P — полномерный многогранник со сложностью граней не более f , то P содержит шар радиуса $2^{-7n^{3}f}$ . При этом этот шар содержится в шаре радиуса $2^{5n^{2}f}$ вокруг начала.

Небольшая сложность представления полезна для «округления» приближенных решений до точных. Конкретно: ^[3]^: 166

Если P — многогранник со сложностью граней не более f , y — рациональный вектор, элементы которого имеют общий знаменатель не более q , а расстояние от y до P не более 2 ^-2-2f/ q , то фактически находится в P. y
Если P — многогранник со сложностью вершин не более v и P удовлетворяет неравенству a ^Тх ≤ б + 2 ^-v-1, то P также удовлетворяет неравенству a ^Тх ≤ б.
Если P — многогранник со сложностью граней не более f , а v — рациональный вектор с расстоянием от P не более 2 ^{-6н ф}, а q и w — целочисленные векторы, удовлетворяющие $\|qv-w\|<2^{-3f},0<q<2^{4nf}$ точка w / q содержится в P. , то Число q и вектор w можно найти в политайме, используя одновременное диофантовое приближение .
Если P — многогранник со сложностью вершин не более v и P удовлетворяет неравенству a ^Тх ≤ б + 2 ^-6nv, а q,c,d — целочисленные векторы, удовлетворяющие $\|qa-c\|+|qb-d|<2^{-3v},0<q<2^{4nv}$ , то P удовлетворяет неравенству c ^ТИкс ≤ д . Числа q,d и вектор c можно найти в политайме, используя одновременное диофантовое приближение .