Oblicz najniższy wymiarowy polytop z danego zestawu wektorów znakowych

Biorąc pod uwagę zestaw hiperpłaszczyzn określonych przez wektory normalne , wszystkie typy komórek (lub wektory znakowe) to wszystkie wektory t ∈ { + , - } m, dla których istnieje wektor tak, że i dla wszystkich . W tym przypadku oznacza wewnętrzny produkt, a oznacza znak ( lub$h_1,\dots,h_m \in \mathbf R^d$$t\in\{+,-\}^m$ ⟨ V , H i ⟩ ≠ 0 T I = sign ( ⟨ V , H i ⟩ ) i ⟨ U , V ⟩ znak ( x ) + - $v\in\mathbf R^d$$\langle v,h_i \rangle \neq 0$$t_i = \text{sign}( \langle v,h_i \rangle )$$i$$\langle u,v\rangle$$\text{sign}(x)$$+$$-$ ) niezerowej liczby rzeczywistej .$x$

Pytanie: Jaki jest najszybciej znany algorytm operacji odwrotnej? Biorąc pod uwagę zestaw typów komórek, chcemy obliczyć pewien zestaw hiperpłaszczyzn w możliwie jak najmniejszej liczbie wymiarów, aby jego typy komórek były nadzbiorem .t 1 , … , t $t_1,\dots,t_n$$t_1,\dots,t_n$

Jest to równoważne obliczeniu rangi znaku macierzy, która jest NP-twarda, jak pokazano w tym artykule . Dlatego nie można oczekiwać zbyt wydajnego algorytmu.