Calcular el politopo dimensional más bajo a partir de un conjunto dado de vectores de signos

11

Dado un conjunto de hiperplanos determinados por los vectores normales , sus tipos de células (o vectores de signos) son todos los vectores t { + , - } m para los que existe un vector v R d de modo que v , h i0 y t i = signo ( v , h i)h1,,hmRdt{+,}mvRdv,hi0ti=sign(v,hi)vale para todo . Aquí, u , v denota el producto interior y signo ( x ) denota el signo ( + o - ) de la no-cero número real x .iu,vsign(x)+x

Pregunta: ¿Cuál es el algoritmo más rápido conocido para la operación inversa? Dado un conjunto de tipos de células, queremos calcular algún conjunto de hiperplanos en la menor cantidad de dimensiones posible, de modo que sus tipos de células sean un superconjunto de t 1 , ... , t n .t1,,tnt1,,tn

Holger
fuente
1
Por cierto, no está claro cuál es el producto interno de un hiperplano y un vector. ¿Tenía intención siendo el vector normal de la i hiperplano -ésimo? hii
Sasho Nikolov
Sí, se supone que son los vectores normales: dije formalmente exactamente lo que estoy buscando.
Holger

Respuestas:

5

Esto es equivalente a calcular el rango de signos de una matriz, que es NP-hard como se muestra en este documento . Por lo tanto, no puede esperar un algoritmo demasiado eficiente.

Sasho Nikolov
fuente