Задача перерахування вершин
У математиці задачею перерахування вершин багатогранника, багатогранного CW-комплексу, Шаблон:Нп або якогось іншого об'єкта дискретної геометрії є задача визначення вершин об'єкта за певного формального подання об'єкта. Класичним прикладом є задача перерахування вершин опуклого багатогранника, заданого системою лінійних нерівностей:
де A — матриця m × n , x — вектор-рядок n-змінних (n × 1), а b — вектор-стовпець, що містить m констант (m × 1).
Складність обчислень
Обчислювальна складність цієї задачі є предметом дослідження у галузі інформатики. Для необмежених багатогранників, як відомо, проблема є NP-складною, точніше, не існує алгоритму, який би виконувався за поліноміальний час від комбінованого розміру вводу-виводу, хіба що P = NP[1].
У статті Шаблон:Нп та Комея Фукуди[2] представлено алгоритм, який знаходить v вершин багатогранника, визначених невиродженою системою n нерівностей в просторі розмірності d (або, дуально, v граней опуклої оболонки n точок у розмірності d, де кожна грань містить рівно d заданих точок) за час O(ndv) та з використанням пам'яті O(nd). v вершин для Шаблон:Нп n гіперплощин у d вимірах можна знайти за час O (n2dv) з використанням пам'яті O(nd). Алгоритм Авіса — Фукуди адаптував Шаблон:Нп для орієнтованих матроїдів.