Проблема с перечислением вершин
В математике проблема перечисления вершин , многогранника комплекса многогранных ячеек , структуры гиперплоскости или какого-либо другого объекта дискретной геометрии объекта — это проблема определения вершин при некотором формальном представлении объекта. Классическим примером является задача перечисления вершин выпуклого многогранника, заданного набором линейных неравенств : [1]
где 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 2 dv O( nd ) временная и пространственная сложность ). Алгоритм Ависа – Фукуды адаптировал алгоритм крест-накрест для ориентированных матроидов.
Примечания
[ редактировать ]- ^ Эрик В. Вайсштейн Краткая математическая энциклопедия CRC, 2002, ISBN 1-58488-347-2 , с. 3154, статья "перечисление вершин"
- ^ Леонид Хачиян; Эндре Борос; Конрад Борис; Халед Эльбассиони; Владимир Гурвич (март 2008 г.). «Построить все вершины многогранника сложно» . Дискретная и вычислительная геометрия . 39 (1–3): 174–190. дои : 10.1007/s00454-008-9050-5 .
- ^ Дэвид Авис; Комей Фукуда (декабрь 1992 г.). «Алгоритм поворота для выпуклых оболочек и перечисления вершин компоновок и многогранников» . Дискретная и вычислительная геометрия . 8 (1): 295–313. дои : 10.1007/BF02293050 .
Ссылки
[ редактировать ]- Авис, Дэвид ; Фукуда, Комэй (декабрь 1992 г.). «Алгоритм поворота для выпуклых оболочек и перечисления вершин компоновок и многогранников» . Дискретная и вычислительная геометрия . 8 (1): 295–313. дои : 10.1007/BF02293050 . МР 1174359 .