Задача перечисления вершин

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

${\displaystyle Ax\leq b}$

где A — матрица m × n , x — вектор-столбец переменных размером n × 1, а b — вектор-столбец констант размером m × 1. Обратная ( двойственная ) задача нахождения ограничивающих неравенств по заданным вершинам называется перечислением граней (см. алгоритмы выпуклой оболочки ).

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

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

• Эйвис, Дэвид ; Фукуда, Комей (декабрь 1992 г.). «Поворотный алгоритм для выпуклых оболочек и перечисления вершин расположений и многогранников». Дискретная и вычислительная геометрия . 8 (1): 295–313. doi : 10.1007/BF02293050 . MR  1174359.