Проблема перечисления вершин - Vertex enumeration problem

В математике проблема перечисления вершин для многогранник, многогранник клеточный комплекс, а расположение гиперплоскости, или какой-то другой объект дискретная геометрия, - это задача определения объекта вершины дано некоторое формальное представление объекта. Классическим примером является проблема перечисления вершин выпуклый многогранник указанный набор линейных неравенств:[1]

куда А является м×п матрица Икс является п× 1 вектор-столбец переменных, и б является м× 1 вектор-столбец констант.

Вычислительная сложность

В вычислительная сложность проблемы является предметом исследования в Информатика. Для неограниченных многогранников проблема, как известно, является NP-сложной, точнее, не существует алгоритма, который работал бы за полиномиальное время при комбинированном размере ввода-вывода, если только P = NP [2].

Статья 1992 г. Дэвид Авис и Комей Фукуда[3] представляет алгоритм, который находит v вершины многогранника, заданного невырожденной системой п неравенство в d размеры (или, вдвойне, v грани из выпуклый корпус из п указывает в d размеры, где каждая грань содержит ровно d данные баллы) во времени О (ndv) и Космос O (nd). В v вершины в простом расположении п гиперплоскости в d размеры можно найти в O (п2dv) время и O (nd) космическая сложность. Алгоритм Ависа – Фукуда адаптировал перекрестный алгоритм для ориентированных матроидов.

Примечания

  1. ^ Эрик В. Вайсштейн CRC Краткая энциклопедия математики, 2002, ISBN  1-58488-347-2, п. 3154, статья "Перечисление вершин"
  2. ^ Леонид Хачиян; Эндре Борос; Конрад Борис; Халед Эльбассиони; Владимир Гурвич (март 2008 г.). «Создать все вершины многогранника сложно». Дискретная и вычислительная геометрия. 39 (1–3): 174–190. Дои:10.1007 / s00454-008-9050-5.
  3. ^ Дэвид Авис; Комей Фукуда (декабрь 1992 г.). «Алгоритм поворота для выпуклых оболочек и нумерация вершин конфигураций и многогранников». Дискретная и вычислительная геометрия. 8 (1): 295–313. Дои:10.1007 / BF02293050.

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