8
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. polymake.org/doku.php/tutorial/apps_topaz $\endgroup$
    – Joseph O'Rourke
    Commented Dec 22, 2010 at 0:39
  • 2
    $\begingroup$ 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. $\endgroup$
    – manifold-destiny
    Commented Dec 22, 2010 at 2:05

1 Answer 1

Reset to default
6
$\begingroup$

The state-of-the-art methods for proving non-polytopality differ from those of proving polytopality of a simplicial sphere $S$. Let me give you an overview:

  • If $S$ is non-polytopal, then one way of proving non-polytopality is to generate all compatible oriented matroids and then show that none of these oriented matroids is realizable. For this, the best methods seems to be the biquadratic final polynomial method by Richter-Gebert and Bokowski. (This mehtod is explained in the book you cite.) For some simplicial spheres with relatively few vertices in low dimension already, there are very many compatible oriented matroid (let's say a million). In these cases it is faster to run the biquadratic final polynomial already on a partial chirotope, consisting of those signs that are determined by the simplicial sphere directly.

  • If $S$ is polytopal, the best way of proving polytopality is giving an explicit realization. To this end we consider the semi-algebraic set that corresponds to the realization space of a polytope with $S$ as a boundary. We set up the corresponding system of non-linear equations and use non-linear solvers to find a solution. The solvers we use employ an branch-and-bound approach together with linear underestimators. Again In a next step we convert the numerical solution into an exact solution, such that it can be checked in exact arithmetic that we found indeed a realization of $S$.

More details can be found in my preprint:

Realizability and inscribability for simplicial polytopes via nonlinear optimization

As one application of these techniques we consider simplicial $3$-spheres with $10$ vertices and decide whether they are polytopal for all of them. There are precisely $247,882$ such spheres; $162,004$ are polytopal and the $85,878$ are non-polytopal. Therefore we obtain a complete classification of all combinatorial types of $4$-polytopes with $10$ vertices.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .