Compute lowest dimensional polytope from a given set of sign vectors
This is equivalent to computing the sign rank of a matrix, which is NP-hard as shown in this paper. So you cannot expect too efficient of an algorithm.