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

Опуклий політоп (англ. Convex polytope) — це спеціальний випадок політопа з додатковою умовою опуклості. У тривимірному просторі опуклий політоп є опуклим многогранником. Опуклий політоп можна визначити як перетин скінченної кількості замкнених півпросторів.

Треба зауважити, що в деяких текстах вимагають від політопів обмеженість, а в інших розглядають без обмежень.

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

Всебічну і впливову роботу за цією темою, під назвою Опуклі політопи, опублікував у 1967 році Бранко Ґрюнбаум. В 2003 році вийшла друга редакція зі значними доповненнями написаними іншими авторами.^[1]

В книзі Ґрюнбаума і в багатьох інших роботах з дискретної геометрії опуклі політопи зазвичай називаються просто «політопами». Ґрюнбаум вказує на те, що можна уникати незліченних повторювань слова «опуклий», і все одно буде зрозуміло, що мова йде про опуклі політопи.

Визначення

Зазвичай опуклий політоп визначається як перетин скінченної кількості замкнених півпросторів Евклідова простору.

Часто додатково припускають, що опуклий політоп є обмеженим. В цьому випадку опуклий політоп можна також визначити як опуклу оболонку скінченної кількості точок.

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

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

Множина K з

\mathbb {R} ^{n}

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

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

Перетин півпросторів

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

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

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

,

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

{\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 є числом півпросторів, що описують політоп. Це можна стисло переписати у вигляді матричної нерівності:

Ax\leqslant b

,

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

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

Пов'язані визначення

Гранню опуклого політопу є перетин політопу півпростором, при якому ніяка внутрішня точка політопу не лежить на межі півпростору. Якщо політоп є d-вимірним, його грані (d − 1)-вимірні, вершини — 0-вимірні грані, ребра — 1-вимірні грані, кромки — (d − 2)-вимірні грані.

Два політопи називаються комбінаторно ізоморфними, якщо їхні ґратки граней ізоморфні.

Граф многогранника — це множина вершин і ребер політопу, грані більших розмірностей ігноруються.

Приклади

В 2-вимірному просторі прикладами тілесних політопів будуть півплощина, стрічка між двома паралельними прямими, кут (перетин двох непаралельних півплощин), фігура, що задається опуклою ламаною з двома променями, приєднаними до кінців, і опуклий многокутник.
Спеціальними випадками необмежених опуклих політопів є шар між двома паралельними гіперплощинами, тілесний двогранний кут утворений двома непаралельними півпросторами, циліндр, необмежена призма і необмежений конус.

Властивості

Кожен (обмежений) опуклий політоп є відображенням симплекса, кожна точка є опуклою комбінацією скінченної кількості вершин. Проте взагалі політопи не ізоморфні симплексам.

Обмежений опуклий політоп, як і будь-яка інша компактна опукла множина $\mathbb {R} ^{n}$ $\mathbb {R} ^{n}$ , гомеоморфний замкненій кулі.^[2] Якщо політоп є тілесним, куля має розмірність $n$ $n$ .
- Зокрема опуклий політоп є многовидом із межею, його ейлерова характеристика дорівнює 1, а його фундаментальна група тривіальна.
- Межа опуклого політопу гомеоморфна (m − 1)-вимірній сфері. Ейлерова характеристика межі дорівнює 0 для парного m і 2 для непарного m. Межу можна розглядати як паркет (m − 1)-вимірної сферичної геометрії, тобто сферичний паркет.

Грані опуклого політопу утворюють ґратку з ейлеровим частковим порядком^[en], яка називається ґраткою граней, де частковий порядок визначається приналежністю граней. Визначення грані, дане вище, дозволяє як сам політоп, так і порожню множину вважати гранями. Весь політоп є єдиним максимальним елементом ґратки, а порожня множина, що є (−1)-вимірною гранню (порожній політоп), є єдиним мінімальним елементом політопу.

Як показав Вітні^[3], ґратка граней тривимірного многогранника визначається його графом. Те ж саме вірно, якщо многогранник є простим (Blind & Mani-Levitska (1987), в книзі Kalai (1988) дане просте доведення). Останній факт є інструментом в доведенні, що з точки зору обчислювальної складності задача визначення, чи є два опуклих многогранники комбінаторно ізоморфними, еквівалентна задачі визначення, чи є графи ізоморфними, навіть якщо обмежитися класами простих або симплексних многогранників.^[4]

Симплексне розкладання

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

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

Опис політопу

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

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

Типи опуклих політопів

Політоп називається тілесним, якщо він є n-вимірним об'єктом простору $\mathbb {R} ^{n}$ .
Простий многогранник

Варіації та узагальнення

Див. також

Теорема Вейля — Мінковського

Примітки

↑ Бранко Ґрюнбаум, Convex Polytopes, 2nd edition, prepared by Volker Kaibel, Victor Klee, and Günter M. Ziegler, 2003, ISBN 0-387-40409-0, ISBN 978-0-387-40409-7, 466 pp.
↑ Glen Bredon^[en]. Topology and Geometry. — 1993. — ISBN 0-387-97926-3, p. 56.
↑ Hassler Whitney. Congruent graphs and the connectivity of graphs // Amer. J. Math. — 1932. — Т. 54, вип. 1. — С. 150–168.
↑ Volker Kaibel, Alexander Schwartz. On the Complexity of Polytope Isomorphism Problems // Graphs and Combinatorics. — 2003. — Т. 19, вип. 2. — С. 215—230. Архівовано з джерела 21 липня 2015. Процитовано 2014-05-09.
↑ B. Büeler, A. Enge, K. Fukuda. Exact Volume Computation for Polytopes: A Practical Study. Polytopes — Combinatorics and Computation.. — 2000. — С. 131. — ISBN 978-3-7643-6351-2. — DOI:10.1007/978-3-0348-8438-9_6..

Посилання

Weisstein, Eric W. Convex polygon(англ.) на сайті Wolfram MathWorld.
Weisstein, Eric W. Convex polyhedron(англ.) на сайті Wolfram MathWorld.
Komei Fukuda, Polyhedral computation FAQ.

[grun-1] Бранко Ґрюнбаум, Convex Polytopes, 2nd edition, prepared by Volker Kaibel, Victor Klee, and Günter M. Ziegler, 2003, ISBN 0-387-40409-0, ISBN 978-0-387-40409-7, 466 pp.

[bredon-2] Glen Bredon^[en]. Topology and Geometry. — 1993. — ISBN 0-387-97926-3, p. 56.

[3] Hassler Whitney. Congruent graphs and the connectivity of graphs // Amer. J. Math. — 1932. — Т. 54, вип. 1. — С. 150–168.

[4] Volker Kaibel, Alexander Schwartz. On the Complexity of Polytope Isomorphism Problems // Graphs and Combinatorics. — 2003. — Т. 19, вип. 2. — С. 215—230. Архівовано з джерела 21 липня 2015. Процитовано 2014-05-09.

[5] B. Büeler, A. Enge, K. Fukuda. Exact Volume Computation for Polytopes: A Practical Study. Polytopes — Combinatorics and Computation.. — 2000. — С. 131. — ISBN 978-3-7643-6351-2. — DOI:10.1007/978-3-0348-8438-9_6..

[1]

[2]

[3]

[4]

[5]

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

Зміст

Визначення