MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The problem of recognizing whether a simplicial face lattice is polytopal is sometimes called the Steinitz problem.

Sturmfels and Bokowski advanced a set of methods in the late 80s to test whether the face lattice of a simplicial sphere was also realizable as a polytope.

The method uses oriented matroids. The problem is NP-hard, so their algorithm requires exponential time in the worst case, but they reported that the algorithm often converged quickly.

In the intervening two decades, I'm sure that newer approaches have been developed. Is there a better method known today? More interestingly, are there any software implementations available that solve this problem -- even using the older approach?

share|cite|improve this question
You might investigate the software polymake. The topaz application of polymake says, "The option geom_real tells the client to compute the GEOMETRIC_REALIZATION." I do not know this well enough to be certain that this would be useful for you. – Joseph O'Rourke Dec 22 '10 at 0:39
Thanks! However, I believe that computing the geometric realization of a simplicial sphere (which is what it looks like Polymake does) is not sufficient to guarantee polytopality. There are known instances where a complex is realizable as a sphere, but where the dual is nonpolytopal. – manifold-destiny Dec 22 '10 at 2:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.