Polytopal and nonpolytopal spheres an algorithmic approach

摘要: The convexity theory for oriented matroids, first developed by Las Vergnas [17], provides the framework a new computational approach to Steinitz problem [13]. We describe an algorithm which, given combinatorial (d − 2)-sphereS withn vertices, determines setC d,n(S) of rankd matroids points and face latticeS. SinceS is polytopal if only there realizableM eC d,n(S), this method together with coordinatizability test in [10] yields decision procedure polytopality large class spheres. As main result we prove that exist 431 types neighborly 5-polytopes 10 vertices establishing coordinates 98 “doubted polytopes” classification Altshuler [1]. show alln ≧k + 5 ≧8 simplicialk-spheres which are non-polytopal due simple fact they fail be matroid On other hand, 3-sphereM 963 9 9 [2] smallest sphere, matroidk-spheres 6 ≧ 9.