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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
3-вимірний опуклий політоп

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

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

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

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

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

Визначення[ред.ред. код]

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

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

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

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

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

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

Перетин півпросторів[ред.ред. код]

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

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

a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \leqslant b,

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

\begin{alignat}{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{alignat},

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

Ax \leqslant b,

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

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

Пов'язані визначення[ред.ред. код]

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

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

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

Приклади[ред.ред. код]

Властивості[ред.ред. код]

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

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

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

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

Опис політопу[ред.ред. код]

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

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

Типи опуклих політопів[ред.ред. код]

Варіації та узагальнення[ред.ред. код]

Посилання[ред.ред. код]

  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, 466pp.
  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 54 (1932) (1) С. 150–168.
  4. Volker Kaibel, Alexander Schwartz On the Complexity of Polytope Isomorphism Problems 19 (2003) (2) С. 215–230.
  5. B. Büeler, A. Enge, K. Fukuda Exact Volume Computation for Polytopes: A Practical Study. Polytopes — Combinatorics and Computation. (2000) С. 131. — DOI:10.1007/978-3-0348-8438-9_6..