Опуклий політоп

В книзі Опуклі політопи Ґрюнбаум визначає опуклий політоп як компактну опуклу множину, зі скінченним числом екстремальних точок:

Множина K з Rⁿ є опуклою, якщо для кожної пари різних точок a, b в K, замкнений сегмент з кінцями a та b міститься в K.

Це еквівалентно визначенню обмеженого опуклого політопа як опуклої оболонки кінцевого числа точок, де кінцева множина має містити множину екстремальних точок політопу. Для компактного опуклого політопу мінімальне представлення через вершини є єдиним і отримується з множини вершин політопу.

Опуклий політоп можна визначити як перетин скінченого числа півпросторів. Існує нескінченне число довільних способів описати політоп через перетин півпросторів. Однак для тілесного опуклого політопу мінімальний опис через півпростори є фактично єдиним і отримується з множини півпросторів, визначених гранями політопа.

Замкнений півпростір може бути записаний лінійною нерівністю:

${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}\leqslant b}$,

де n є розмірністю простору, що містить політоп, який розглядають. Отже замкнений опуклий політоп можна розглядати як множину рішень системи лінійних нерівностей:

${\displaystyle {\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\cdots +\;&&a_{1n}x_{n}&&\;\leqslant \;&&&b_{1}\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\cdots +\;&&a_{2n}x_{n}&&\;\leqslant \;&&&b_{2}\\\vdots \;\;\;&&&&\vdots \;\;\;&&&&\vdots \;\;\;&&&&&\;\vdots \\a_{m1}x_{1}&&\;+\;&&a_{m2}x_{2}&&\;+\cdots +\;&&a_{mn}x_{n}&&\;\leqslant \;&&&b_{m}\\\end{alignedat}}}$,

де m є числом півпросторів, що описують політоп. Це можна стисло переписати у вигляді матричної нерівності:

${\displaystyle Ax\leqslant b}$,

де A є m×n матрицею, x є n×1 вектор-стовпець змінних, і b є постійним m×1 вектор-стовпцем.

Відкритий опуклий політоп задається заміною нестрогих нерівностей на строгі у попередньому визначенні. Коефіцієнти кожного рядку A і b відповідають коефіцієнтам лінійної нерівності, що визначає відповідний півпростір. Отже кожний рядок матриці відповідає опорній гіперплощині політопу, тобто гіперплощині, що обмежує півпростір, який містить політоп. Якщо опорна гіперплощина перетинає політоп, вона називається обмежувальною гіперплощиною (оскільки вона є опорною, вона може перетинати політоп тільки за його межею).

Опуклий політоп можна розкласти на симпліціальний комплекс або об'єднання симплексів, що задовольняє певним властивостям.

Якщо задано опуклий r-вимірний політоп P, підмножина його вершин, що містить (r+1) афінно незалежних точок, дає r-симплекс. Можна утворити набір підмножин таких, що об'єднання відповідних симплексів дорівнює P і перетин будь-яких двох симплексів або порожній, або симплекс меншої розмірності. Цей симплексний розклад служить базисом для багатьох методів обчислення об'єму опуклого політопу, оскільки об'єм симплексу легко обчислити.[5]

Різні описи опуклого політопу мають різні властивості, тому запис або побудова одного представлення за заданим іншим поданням є важливою задачею. Задача побудови V-подання відома як задача перерахування вершин, а задача побудови H-подання відома як задача перерахування граней. Хоча множина вершин обмеженого опуклого політопу визначає його єдиним чином, в різних додатках важливо знати більше про комбінаторну структуру політопу, тобто про ґратку граней. Різні алгоритми обчислення опуклої оболонки мають справу як з перерахуванням граней, так і з побудовою ґратки граней.

У випадку площини, тобто для опуклого многокутника, задачі перерахування як ребер, так і вершин, означають упорядкування вершин (або, відповідно, ребер) навколо опуклої оболонки. Задача тривіальна, якщо опуклий многокутник заданий традиційним для многокутників способом, тобто впорядкованою послідовністю його вершин ${\displaystyle v_{1},\dots ,v_{m}}$. Якщо заданий перелік вершин (або ребер) не впорядкований, часова складність задачі стає O(m log h), де m — число точок, для яких відшукується опукла оболонка, а h — число вершин в фінальному многокутнику (див. алгоритм Чена).