Problem z wyliczaniem wierzchołków
W matematyce problem wyliczania wierzchołków dla polytopu , wielościennego kompleksu komórek , układu hiperpłaszczyzny lub innego obiektu o dyskretnej geometrii jest problemem określenia wierzchołków obiektu przy pewnej formalnej reprezentacji obiektu. Klasycznym przykładem jest problem wyliczania wierzchołków polytopu wypukłego określonego przez zbiór nierówności liniowych :
gdzie A jest macierzą m × n , x jest wektorem kolumnowym zmiennych n × 1, a b jest wektorem kolumnowym stałych m × 1. Odwrotny ( podwójny ) problem znajdowania nierówności ograniczających przy danych wierzchołkach nazywa się wyliczaniem aspektów (patrz algorytmy wypukłego kadłuba ).
Złożoność obliczeniowa
Złożoność obliczeniowa problemu jest przedmiotem badań w informatyce . W przypadku nieograniczonych wielościanów problem jest znany jako NP-trudny, a dokładniej, nie ma algorytmu, który działałby w czasie wielomianowym w połączonym rozmiarze wejścia-wyjścia, chyba że P = NP.
Artykuł Davida Avisa i Komei Fukudy z 1992 roku przedstawia algorytm wyszukiwania wstecznego , który znajduje wierzchołki v polytope zdefiniowane przez niezdegenerowany system n nierówności w d wymiarach (lub podwójnie, v ścianki wypukłego kadłuba n punktów w d wymiarów, gdzie każda ścianka zawiera dokładnie d danych punktów) w czasie O ( ndv ) i przestrzeni O( nd ). Wierzchołki v w prostym układzie n hiperpłaszczyzn w d wymiarach można znaleźć w złożoności czasowej O( n 2 dv ) i przestrzennej O ( nd ). Algorytm Avis-Fukuda zaadaptował algorytm krzyżowy dla zorientowanych matroidów.
Notatki
- Awis, Dawid ; Fukuda, Komei (grudzień 1992). „Algorytm obracania dla wypukłych kadłubów i wyliczania wierzchołków układów i wielościanów” . Dyskretna i obliczeniowa geometria . 8 (1): 295–313. doi : 10.1007/BF02293050 . MR 1174359 .