This is a cross-post from MathOverflow.

The problem of testing whether a simplicial face lattice (informally, a poset of faces) 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. Lars Schewe has recently shown that the same method can be adapted to make use of optimized SAT solvers, although the underlying technique seems to be the same.

I'm curious if newer approaches have been developed in the intervening decades since Sturmfels and Bokowski published their result. Is their method still the state of the art? Further, are there any software implementations available that solve this problem -- even using the older approach?

In the MathOverflow discussion, Joe O'Rourke pointed out that Polymake has a feature that seems to compute geometric realizations of simplicial complexes [GEOMETRIC_REALIZATION], but this doesn't guarantee polytopality as far as I know.


This is not an answer, just a comment. Frank Lutz in Berlin is one of the experts on this topic, and you might ask him. He maintains a nice web page, The Manifold Page, which includes lots of information and references, including descriptions of Barnette's non-polytopal 3-sphere and Grünbaum-Sreedharan's non-polytopal 3-sphere.

Incidentally, I believe this related problem is still open (if not, I'd like to know of its resolution):

Does every triangulation of a genus 1 torus have a geometric realization (embedding) in $\mathbb{R^3}$?

For sufficiently large genus (I think 5?), there are non-realizable examples.

  • $\begingroup$ Joseph, the link seems to be broken. $\endgroup$ – ilyaraz Sep 26 '11 at 5:11
  • $\begingroup$ @ilyaraz: Thanks; the page moved. I've relinked it. $\endgroup$ – Joseph O'Rourke Sep 26 '11 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.