Calculer le polytope de dimension la plus basse à partir d'un ensemble donné de vecteurs de signe

Etant donné un ensemble d'hyperplans déterminé par les vecteurs normaux , ses types de cellules (ou vecteurs de signe) sont tous des vecteurs t ∈ { + , - } m pour lesquels il existe un vecteur v ∈ R d de sorte que ⟨ v , h i ⟩ ≠ 0 et t i = signe ( ⟨ v , h i ⟩ $h_1,\dots,h_m \in \mathbf R^d$$t\in\{+,-\}^m$$v\in\mathbf R^d$$\langle v,h_i \rangle \neq 0$$t_i = \text{sign}( \langle v,h_i \rangle )$vaut pour tout . Ici, ⟨ u , v ⟩ désigne le produit scalaire et signe ( x ) représente le signe ( + ou - ) du nombre réel non nul x .$i$$\langle u,v\rangle$$\text{sign}(x)$$+$$-$$x$

Question: Quel est l'algorithme connu le plus rapide pour l'opération inverse? Etant donné un ensemble de types de cellules, nous voulons calculer un ensemble d'hyperplans dans le moins de dimensions possible, afin que ses types de cellules soient un sur-ensemble de t 1 , … , t n .$t_1,\dots,t_n$$t_1,\dots,t_n$

Cela équivaut à calculer le rang de signe d'une matrice, qui est NP-difficile comme indiqué dans cet article . Vous ne pouvez donc pas vous attendre à un algorithme trop efficace.