Задача перерахування вершин

У математиці задачею перерахування вершин багатогранника, багатогранного CW-комплексу, конфігурації гіперплощин або якогось іншого об'єкта дискретної геометрії є задача визначення вершин об'єкта за певного формального подання об'єкта. Класичним прикладом є задача перерахування вершин опуклого багатогранника, заданого системою лінійних нерівностей:

$Ax\leqslant b$

де A — матриця m × n , x — вектор-рядок n-змінних (n × 1), а b — вектор-стовпець, що містить m констант (m × 1).

Складність обчислень

Обчислювальна складність цієї задачі є предметом дослідження у галузі інформатики. Для необмежених багатогранників, як відомо, проблема є NP-складною, точніше, не існує алгоритму, який би виконувався за поліноміальний час від комбінованого розміру вводу-виводу, хіба що P = NP.

У статті Давида Авіса та Комея Фукуди представлено алгоритм, який знаходить v вершин багатогранника, визначених невиродженою системою n нерівностей в просторі розмірності d (або, дуально, v граней опуклої оболонки n точок у розмірності d, де кожна грань містить рівно d заданих точок) за час O(ndv) та з використанням пам'яті O(nd). v вершин для конфігурації n гіперплощин у d вимірах можна знайти за час O (n²dv) з використанням пам'яті O(nd). Алгоритм Авіса — Фукуди адаптував перехресний алгоритм для орієнтованих матроїдів.

Список літератури

• Avis, David; Fukuda, Komei (Грудень 1992). A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete and Computational Geometry. 8: 295—313. doi:10.1007/BF02293050. MR 1174359.