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

Трехмерный выпуклый многогранник

А выпуклый многогранник это частный случай многогранник, обладающий дополнительным свойством, что он также является выпуклый набор содержится в ${ displaystyle n}$-мерное евклидово пространство ${ Displaystyle mathbb {R} ^ {п}}$. Большинство текстов^[1][2] используйте термин "многогранник" для ограниченный выпуклый многогранник и слово «многогранник» для более общего, возможно, неограниченного объекта. Другие^[3] (включая эту статью) позволяют многогранникам быть неограниченными. Термины «ограниченный / неограниченный выпуклый многогранник» будут использоваться ниже всякий раз, когда ограниченность критична для обсуждаемого вопроса. В других текстах выпуклый многогранник отождествляется с его границей.

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

Во влиятельных учебниках Грюнбаума^[1] и Циглер^[2] по теме, а также во многих других текстах в дискретная геометрия, выпуклые многогранники часто называют просто многогранниками. Грюнбаум указывает, что это сделано исключительно для того, чтобы избежать бесконечного повторения слова «выпуклый», и что все обсуждения следует понимать как относящиеся только к выпуклой разновидности (стр. 51).

Многогранник называется полномасштабный если это ${ displaystyle n}$-мерный объект в ${ Displaystyle mathbb {R} ^ {п}}$.

Примеры

• Много примеров ограниченных выпуклых многогранников можно найти в статье "многогранник ".
• В двумерном случае полномерными примерами являются полуплоскость, полоса между двумя параллельными линиями, угол shape (пересечение двух непараллельных полуплоскостей), форма определяется выпуклым многоугольная цепь с двумя лучи прикреплен к его концам, и выпуклый многоугольник.
• Частные случаи неограниченного выпуклого многогранника - это плита между двумя параллельными гиперплоскостями, клин, определяемый двумя непараллельными полупространства, а многогранный цилиндр (бесконечный призма ), а многогранный конус (бесконечный конус ), определяемые тремя или более полупространствами, проходящими через общую точку.

Определения

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

Вершинное представление (выпуклая оболочка)

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

Множество ${ displaystyle K}$ из ${ Displaystyle mathbb {R} ^ {п}}$ является выпуклый если для каждой пары различных точек ${ displaystyle a}$, ${ displaystyle b}$ в ${ displaystyle K}$, замкнутый отрезок с конечными точками ${ displaystyle a}$ и ${ displaystyle b}$ содержится в ${ displaystyle K}$.

Это эквивалентно определению ограниченного выпуклого многогранника как выпуклый корпус конечного множества точек, причем конечное множество должно содержать множество крайних точек многогранника. Такое определение называется представление вершины (V-образное представление или же V-описание).^[1] Для компактного выпуклого многогранника минимальное V-описание единственно и задается множеством вершины многогранника.^[1] Выпуклый многогранник называется интегральный многогранник если все его вершины имеют целочисленные координаты.

Пересечение полупространств

Выпуклый многогранник можно определить как пересечение конечного числа полупространств. Такое определение называется представление полупространства (H-представление или же H-описание).^[1] Существует бесконечно много H-описаний выпуклого многогранника. Однако для полномерного выпуклого многогранника минимальное H-описание фактически единственно и задается множеством грань -определение полупространств.^[1]

А закрытое полупространство можно записать как линейное неравенство:^[1]

${ displaystyle a_ {1} x_ {1} + a_ {2} x_ {2} + cdots + a_ {n} x_ {n} leq b}$

куда ${ displaystyle n}$ - размерность пространства, содержащего рассматриваемый многогранник. Следовательно, a замкнутый выпуклый многогранник можно рассматривать как набор решений система линейных неравенств:

${ displaystyle { begin {alignat} {7} a_ {11} x_ {1} && ; + ; && a_ {12} x_ {2} && ; + cdots + ; && a_ {1n} x_ {n } && ; leq ; &&& b_ {1} a_ {21} x_ {1} && ; + ; && a_ {22} x_ {2} && ; + cdots + ; && a_ {2n} x_ {n} && ; leq ; &&& b_ {2} vdots ; ; ; &&&& vdots ; ; ; &&&& vdots ; ; ; &&&&&& ; vdots a_ {m1} x_ {1} && ; + ; && a_ {m2} x_ {2} && ; + cdots + ; && a_ {mn} x_ {n} && ; leq ; &&& b_ {m} конец {выровненный}}}$

куда ${ displaystyle m}$ - количество полупространств, определяющих многогранник. Кратко это можно записать как матрица неравенство:

${ Displaystyle Ax leq b}$

куда ${ displaystyle A}$ является ${ Displaystyle м раз п}$ матрица ${ displaystyle x}$ является ${ Displaystyle п раз 1}$ вектор-столбец, координаты которого являются переменными ${ displaystyle x_ {1}}$ к ${ displaystyle x_ {n}}$, и ${ displaystyle b}$ является ${ displaystyle m times 1}$ вектор-столбец, координаты которого являются правыми частями ${ displaystyle b_ {1}}$ к ${ displaystyle b_ {m}}$ скалярных неравенств.

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

Коэффициенты каждой строки ${ displaystyle A}$ и ${ displaystyle b}$ соответствуют коэффициентам линейного неравенства, определяющим соответствующее полупространство. Следовательно, каждой строке в матрице соответствует поддерживающая гиперплоскость многогранника - гиперплоскость, ограничивающая полупространство, содержащее многогранник. Если опорная гиперплоскость также пересекает многогранник, она называется ограничивающая гиперплоскость (поскольку это опорная гиперплоскость, она может пересекать многогранник только на границе многогранника).

Приведенное выше определение предполагает, что многогранник является полномерным. В этом случае есть уникальный минимальный набор определяющих неравенств (с точностью до умножения на положительное число). Неравенства, принадлежащие этой единственной минимальной системе, называются существенный. Множество точек многогранника, удовлетворяющих существенному неравенству с равенством, называется грань.

Если многогранник не является полномерным, то решения ${ Displaystyle Ax leq b}$ лежать в правильном аффинное подпространство из ${ Displaystyle mathbb {R} ^ {п}}$ и многогранник можно изучать как объект в этом подпространстве. В этом случае существуют линейные уравнения, которым удовлетворяют все точки многогранника. Добавление одного из этих уравнений к любому из определяющих неравенств не меняет многогранника. Поэтому, вообще говоря, не существует единственного минимального набора неравенств, определяющих многогранник.

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

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

Два представления вместе обеспечивают эффективный способ решить, включен ли данный вектор в данный выпуклый многогранник: чтобы показать, что он входит в многогранник, достаточно представить, что это выпуклая комбинация вершин многогранника (V-описание используется); чтобы показать, что он не входит в многогранник, достаточно указать одно определяющее неравенство, которое он нарушает.^[4]:256

Тонкий момент в представлении векторами заключается в том, что количество векторов может быть экспоненциальным в измерении, поэтому доказательство того, что вектор находится в многограннике, может быть экспоненциально длинным. К счастью, Теорема Каратеодори гарантирует, что каждый вектор в многограннике может быть представлен не более чем d+1 определяющих векторов, где d это размерность пространства.

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

Для неограниченного многогранника (иногда называемого многогранником) H-описание все еще действует, но V-описание должно быть расширено. Теодор Моцкин (1936) доказал, что любой неограниченный многогранник можно представить в виде суммы ограниченный многогранник и выпуклый многогранный конус.^[5] Другими словами, каждый вектор в неограниченном многограннике является выпуклая сумма его вершин (его "определяющих точек"), плюс коническая сумма из Евклидовы векторы его бесконечных граней (его «определяющих лучей»). Это называется теорема о конечном базисе.^[3]

Характеристики

Каждый (ограниченный) выпуклый многогранник является образом симплекс, так как каждая точка выпуклое сочетание (конечного числа) вершин. Однако многогранники, вообще говоря, не изоморфны симплексам. Это в отличие от случая векторные пространства и линейные комбинации причем каждое конечномерное векторное пространство является не только образом, но и фактически изоморфно евклидову пространству некоторой размерности (или аналогу над другими полями).

Решетка для лица

А лицо выпуклого многогранника - это любое пересечение многогранника с полупространство такое, что ни одна из внутренних точек многогранника не лежит на границе полупространства. Эквивалентно грань - это множество точек, дающих равенство в некотором действительном неравенстве многогранника.^[4]:258

Если многогранник d-размерный, его грани это его (d - 1) -мерные грани, его вершины его 0-мерные грани, его края его одномерные грани, а его гребни это его (d - 2) -мерные грани.

Для выпуклого многогранника п определяемое матричным неравенством ${ Displaystyle Ax leq b}$, если каждая строка в А соответствует ограничивающей гиперплоскости и является линейно независимый остальных рядов, затем каждую грань п соответствует ровно одной строке А, наоборот. Каждая точка на данной грани будет удовлетворять линейному равенству соответствующей строки в матрице. (Это может или не может также удовлетворять равенству в других строках). Аналогично, каждая точка на гребне удовлетворяет равенству в двух строках А.

Решетка граней квадратная пирамида, нарисованный как Диаграмма Хассе; каждая грань в решетке помечена своим набором вершин.

В общем, (п − j) -мерная грань удовлетворяет равенству в j конкретные ряды А. Эти строки образуют основа лица. С геометрической точки зрения это означает, что грань - это множество точек на многограннике, лежащих в пересечении j ограничивающих гиперплоскостей многогранника.

Таким образом, грани выпуклого многогранника образуют Эйлеров решетка назвал его лицевая решетка, где частичное упорядочение - набор граней. Приведенное выше определение грани позволяет рассматривать как сам многогранник, так и пустое множество как грани, гарантируя, что каждая пара граней имеет соединение и встречу в решетке граней. Весь многогранник является единственным максимальным элементом решетки, а пустое множество, рассматриваемое как (−1) -мерная грань (a нулевой многогранник) каждого многогранника является единственным минимальным элементом решетки.

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

В граф многогранников (многогранный граф, график многогранника, 1-скелет) - это набор только вершин и ребер многогранника, без учета граней более высоких измерений. Например, многогранный граф - граф многогранника трехмерного многогранника. В результате Уитни^[6] решетка граней трехмерного многогранника определяется его графиком. То же верно и для простые многогранники произвольной размерности (Blind & Mani-Levitska 1987, доказывая гипотезу Миха Перлес ).^[7] Калаи (1988)^[8] дает простое доказательство, основанное на уникальная ориентация раковины. Поскольку решетки граней этих многогранников определяются их графами, проблема определения того, являются ли два трехмерных или простых выпуклых многогранника комбинаторно изоморфными, может быть эквивалентно сформулирована как частный случай многогранников. проблема изоморфизма графов. Однако можно также перевести эти проблемы в противоположном направлении, показывая, что проверка изоморфизма многогранников является полной изоморфизмом графов.^[9]

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

Выпуклый многогранник, как и любое компактное выпуклое подмножество в р^п, является гомеоморфный закрытому мяч.^[10] Позволять м обозначим размерность многогранника. Если многогранник полномерный, то м = п. Таким образом, выпуклый многогранник является м-размерный многообразие с границей, его Эйлерова характеристика равно 1, а его фундаментальная группа тривиально. Граница выпуклого многогранника гомеоморфна (м - 1) -сфера. Эйлерова характеристика границы равна 0 при четном м и 2 для нечетных м. Границу также можно рассматривать как мозаика из (м - 1) -мерный сферическое пространство - т.е. как сферическая черепица.

Симплициальное разложение

Выпуклый многогранник можно разложить на симплициальный комплекс, или объединение симплексы, удовлетворяющие определенным свойствам.

Учитывая выпуклый р-мерный многогранник п, подмножество его вершин, содержащее (р+1) аффинно независимый очков определяет р-суплекс. Можно сформировать такой набор подмножеств, что объединение соответствующих симплексов равно п, а пересечение любых двух симплексов либо пусто, либо является симплексом меньшей размерности. Это симплициальное разложение лежит в основе многих методов вычисления объема выпуклого многогранника, поскольку объем симплекса легко определяется формулой.^[11]

Алгоритмические задачи для выпуклого многогранника

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

Различные представления выпуклого многогранника имеют разную полезность, поэтому построение одного представления по другому является важной проблемой. Проблема построения V-представления известна как проблема перечисления вершин а проблема построения H-представления известна как проблема перечисления фасетов. Хотя множество вершин ограниченного выпуклого многогранника однозначно определяет его, в различных приложениях важно знать больше о комбинаторной структуре многогранника, т.е. о решетке его граней. Разные алгоритмы выпуклой оболочки имеют дело как с нумерацией граней, так и с построением решетки граней.

В плоском случае, т. Е. Для выпуклый многоугольник, проблемы перечисления фасетов и вершин сводятся к упорядочиванию вершин (соответственно ребер) вокруг выпуклой оболочки. Это тривиальная задача, когда выпуклый многоугольник задан в традиционном для полигоны способом, т.е. упорядоченной последовательностью его вершин ${ displaystyle v_ {1}, dots, v_ {m}}$. Когда входной список вершин (или ребер) неупорядочен, временная сложность проблем становится О (м бревном).^[12] Соответствие нижняя граница известно в алгебраическое дерево решений модель вычисления.^[13]

Расчет объема

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

Смотрите также

• Ориентированный матроид
• Многогранник Нефа
• Теорема Стейница для выпуклых многогранников

Рекомендации

внешняя ссылка

• Вайсштейн, Эрик В. «Выпуклый многоугольник». MathWorld.
• Вайсштейн, Эрик В. «Выпуклый многогранник». MathWorld.
• Комей Фукуда, Часто задаваемые вопросы о многогранных вычислениях.