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

У математиці задачею перерахування вершин багатогранника, багатогранного 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). Алгоритм Авіса — Фукуди адаптував перехресний алгоритм для орієнтованих матроїдів.

Примітки
  1. Leonid Khachiyan; Endre Boros; Konrad Borys; Khaled Elbassioni; Vladimir Gurvich (March 2008). Generating All Vertices of a Polyhedron Is Hard. Discrete and Computational Geometry 39: 174–190. doi:10.1007/s00454-008-9050-5. Проігноровано невідомий параметр |doi-access= (довідка)
  2. David Avis; Komei Fukuda (December 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. Проігноровано невідомий параметр |doi-access= (довідка)

Список літератури
  • 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. MR 1174359. doi:10.1007/BF02293050. Проігноровано невідомий параметр |doi-access= (довідка)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.