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

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

${\displaystyle Ax\leqslant b}$

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

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

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

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

Примітки

1. Leonid Khachiyan; Endre Boros; Konrad Borys; Khaled Elbassioni; Vladimir Gurvich (March 2008). Generating All Vertices of a Polyhedron Is Hard. . 39: 174—190. doi:10.1007/s00454-008-9050-5.
2. David Avis; Komei Fukuda (December 1992). A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. . 8: 295—313. doi:10.1007/BF02293050.

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

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