В математике проблема перечисления вершин для многогранника , многогранного клеточного комплекса , расположения гиперплоскостей или какого-либо другого объекта дискретной геометрии - это проблема определения вершин объекта при некотором формальном представлении объекта. Классическим примером является задача перечисления вершин выпуклого многогранника, задаваемого набором линейных неравенств : [1]
где A - матрица размера m × n , x - вектор-столбец переменных n × 1, а b - вектор-столбец констант размером m × 1.
Вычислительная сложность
Вычислительная сложность задачи является предметом исследований в области информатики . Для неограниченных многогранников проблема, как известно, NP-трудная, точнее, не существует алгоритма, который работал бы за полиномиальное время при комбинированном размере ввода-вывода, если только P = NP. [2]
А 1992 статья Дэвид Avis и Комэй Фукуда [3] представляет собой алгоритм , который находит v вершины многогранника , определяемой невырожденной системы п неравенств в д измерениях (или, дуально, то V фасеты по выпуклой оболочки из п точек d измерений, где каждая грань содержит ровно d заданных точек) во времени O ( ndv ) и пространстве O ( nd ). В V вершины в простом расположении п гиперплоскостей в д размеров могут быть найдены в O ( п 2 Dv ) время и O ( е ) пространства сложность. Алгоритм Ависа – Фукуда адаптировал алгоритм крест-накрест для ориентированных матроидов.
Заметки
- ^ Эрик В. Вайсштейн CRC Краткая энциклопедия математики, 2002, ISBN 1-58488-347-2 , стр. 3154, статья "Перечисление вершин"
- ^ Леонид Хачиян; Эндре Борос; Конрад Борис; Халед Эльбассиони; Владимир Гурвич (март 2008 г.). «Создать все вершины многогранника сложно» . Дискретная и вычислительная геометрия . 39 (1–3): 174–190. DOI : 10.1007 / s00454-008-9050-5 .
- ^ Дэвид Авис; Комей Фукуда (декабрь 1992 г.). «Алгоритм поворота для выпуклых оболочек и нумерация вершин конфигураций и многогранников» . Дискретная и вычислительная геометрия . 8 (1): 295–313. DOI : 10.1007 / BF02293050 .
Рекомендации
- Авис, Дэвид ; Фукуда, Комей (декабрь 1992 г.). «Алгоритм поворота для выпуклых оболочек и нумерация вершин конфигураций и многогранников» . Дискретная и вычислительная геометрия . 8 (1): 295–313. DOI : 10.1007 / BF02293050 . Руководство по ремонту 1174359 .