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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
3-мерный выпуклый многогранник

Выпуклый многогранник — частный случай многогранника, пересечение конечного числа замкнутых полупространств.

Иногда термин «многогранник» используется для обозначения выпуклого многогранника.

Определения[править | править вики-текст]

Обычно выпуклый многогранник определяется как пересечение конечного числа замкнутых полупространств Евклидова пространства.

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

Связанные определения[править | править вики-текст]

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

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

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

Примеры[править | править вики-текст]

Свойства[править | править вики-текст]

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

Симплексное разложение[править | править вики-текст]

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

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

Построение представлений[править | править вики-текст]

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

В случае плоскости, то есть для выпуклого многоугольника, задачи перечисления как рёбер, так и вершин, означают упорядочение вершин (или, соответственно, рёбер) вокруг выпуклой оболочки. Задача тривиальна, если выпуклый многогранник задан традиционным для многоугольников способом, то есть упорядоченной последовательностью его вершин v_1,\dots, v_m. Если входной список вершин (или рёбер) не отсортирован, временна́я сложность задачи становится O(m log h) , где m — число точек, для которых ищется выпуклая оболочка, а h — число вершин в результирующем многограннике (смотрите Алгоритм Чана).

Типы выпуклых многогранников[править | править вики-текст]

  • Многогранник называется телесным, если он является n-мерным объектом пространства Rn.
  • Простой многогранник

Вариации и обобщения[править | править вики-текст]

Ссылки[править | править вики-текст]

  1. Glen Bredon[en] Topology and Geometry. — 1993. — ISBN 0-387-97926-3, p. 56..
  2. Hassler Whitney Congruent graphs and the connectivity of graphs // Amer. J. Math.. — 1932. — В. 1. — Т. 54. — С. 150–168.
  3. Volker Kaibel, Alexander Schwartz {{{заглавие}}} // Graphs and Combinatorics. — 2003. — В. 2. — Т. 19. — С. 215–230.
  4. 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.

Внешние ссылки[править | править вики-текст]