Polytopal and nonpolytopal spheres. An algorithmic approach (Q1100441)

The paper deals with the Steinitz problem, i.e. the decision problem whether a given (d-1)-dimensional combinatorial sphere is isomorphic to the boundary complex of a d-polytope, the problem being unsolved for dimensions \(d\geq 4\) and \(n\geq d+4\) vertices. A new computational approach is given using oriented matroids. It is shown that for all \(n\geq d+4\) and \(d\geq 4\) there exist simplicial \((d-1)-\)spheres with n vertices which are non-matroid-spheres (and therefore nonpolytopal) and also for all \(n\geq d+5\) and \(d\geq 4\) matroid-(d-1)-spheres with n vertices which are nonpolytopal. Their new methods enables the authors to complete Altshuler's enumeration of neighbourly 4-polytopes with 10 vertices [\textit{A. Altshuler}, Can. J. Math. 29, 225-420 (1977; Zbl 0331.57006)] ending up with 431 combinatorial types of such polytopes.