<p>This is equivalent to computing the sign rank of a matrix, which is NP-hard as shown in <a href="http://www.math.rutgers.edu/~sk1233/signrankNP.pdf" rel="noreferrer">this paper</a>. So you cannot expect too efficient of an algorithm.</p>

CC BY-SA 3.0
2015-06-27T00:20:05.407Z
2015-06-27T00:20:05.407Z
Sasho Nikolov
<p>Given a set of hyperplanes determined by the normal vectors $h_1,\dots,h_m \in \mathbf R^d$, its <em>cell types</em> (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$.</p>

<p><strong>Question:</strong> 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$.</p>

CC BY-SA 3.0
2015-06-27T00:20:49.113Z
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
CC BY-SA 3.0
2015-06-28T13:16:39.600Z
Yes, they're supposed to be the normal vectors - I stated formally exactly what I'm looking for.
Holger
<co.combinatorics><cg.comp-geom><computational-geometry><metric-spaces>
Compute lowest dimensional polytope from a given set of sign vectors
Holger
# Compute lowest dimensional polytope from a given set of sign vectors

(Asked by: username_0 on 2015-06-16)

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$.

**Tags:** co.combinatorics, cg.comp-geom, computational-geometry, metric-spaces

> **Comments:**
> **username_1**: 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?  
> **username_0**: Yes, they're supposed to be the normal vectors - I stated formally exactly what I'm looking for.  

---

## 1 answers

### Answer by username_1 on 2015-06-27. Score: 5 | Accepted answer

This is equivalent to computing the sign rank of a matrix, which is NP-hard as shown in [this paper](http://www.math.rutgers.edu/~sk1233/signrankNP.pdf). So you cannot expect too efficient of an algorithm.


---

