# Compute lowest dimensional polytope from a given set of sign vectors

Given a set of hyperplanes determined by the normal vectors $h_1,\dots,h_m \in \mathbf R^d$, its cell types (or sign vectors) are all vectors $t\in\{+,-\}^m$ for which there exists a vector $v\in\mathbf R^d$ so that $\langle v,h_i \rangle \neq 0$ and $t_i = \text{sign}( \langle v,h_i \rangle )$ holds for all $i$. Here, $\langle u,v\rangle$ denotes the inner product and $\text{sign}(x)$ denotes the sign ($+$ or $-$) of the non-zero real number $x$.

Question: What is the fastest known algorithm for the inverse operation? Given a set $t_1,\dots,t_n$ of cell types, we want to compute some set of hyperplanes in as few dimensions as possible, so that its cell types are a superset of $t_1,\dots,t_n$.

• BTW it is not clear what is the inner product of a hyperplane and a vector. Did you intend $h_i$ to be the normal vector of the $i$-th hyperplane? – Sasho Nikolov Jun 27 '15 at 0:20
• Yes, they're supposed to be the normal vectors - I stated formally exactly what I'm looking for. – Holger Jun 28 '15 at 13:16