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

11

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 i0 et t i = signe ( v , h i)h1,,hmRdt{+,}mvRdv,hi0ti=sign(v,hi)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 .iu,vsign(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 .t1,,tnt1,,tn

Holger
la source
1
BTW, il n'est pas clair quel est le produit intérieur d'un hyperplan et d'un vecteur. Souhaitiez-vous que soit le vecteur normal du i- ème hyperplan? hii
Sasho Nikolov
Oui, ils sont censés être les vecteurs normaux - j'ai déclaré formellement exactement ce que je cherchais.
Holger

Réponses:

5

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.

Sasho Nikolov
la source