Cellular decomposition of a sphere to polytope

Question

My primary question is: given a cellular decomposition of a sphere is there any way to check if it can be embedded as the boundary of a polytope?

My question is motivated by the following problem. I began with a polyhedral cell complex $P$ homeomorphic to a ball. Then I had an unbounded polyhedral cone $C$ of the same dimension as $P$. I made the cone homeomorphic to a ball by taking its intersection with a ball sufficiently large so that all the bounded portions of the cone were not changed. Call this new polyhedral ball $C^*$. Then I defined a continuous mapping from $\partial C^*$ to $\partial P$ and used the pasting lemma to define my cellular decomposition of the resulting sphere.

Since I am beginning with two polyhedral objects I would like to end up with something polyhedral, in this case a polytope. My method seems equivalent to "blocking" the unbounded portion of the cone with $P$, which seems should remain polyhedral.

Answer 1

The "primary question" is a well-known hard problem, and I think this reference:

MR0889977 (89b:52009) Reviewed Bokowski, Jürgen(D-DARM); Sturmfels, Bernd(D-DARM) Polytopal and nonpolytopal spheres: an algorithmic approach. Israel J. Math. 57 (1987), no. 3, 257–271. 52A25 (05B35) PDF Clipboard Journal Article Make Link

Is still close to the last word 25 years later (maybe @GilKalai can correct me).

Answer 2

Indeed the primary question is a well-known hard problem. To have a chance to be a polytope, the cellular decomposition should be regular (the closure of an open cell must be a closed cell) and satisfies the lattice property (The intersection of two cells must be a cell - possibly empty). It also needed to be a polyhedral complex - each cell by itself should be combinatorially equivalent to a polytope. These conditions are sufficient for 2-spheres by a fundamental theorem of Steinitz (and also when the number of vertices is at most the dimension plus 4) but not for d-spheres for $d>2$. The smallest examples of polyhedral spheres which are non-polytopal are 3-spheres with 8 vertices.

Answer 3

The question reminds me of the idea behind David W. Jones's 1984 Bangor thesis on "Poly-T-complexes" available here, as follows: we have globular sets, simplicial sets, cubical sets, but what is wrong with pentagons, and why is there a prejudice against rhombic dodecahedra? Also the part of geometric group theory known as "van Kampen diagrams" uses complicated 2-dimensional diagrams to deduce consequences of relations. There are also families of polyhedra such as Stasheff polyhedra.

David defined quite general "cone complexes" with a shelling criterion to avoid some wild examples. In order to model some group theory, and to define polyhedral sets, he also defined "marked cone complexes"; this allows the modelling of the relations $ x^3=1 $, $ xyx=yxy $, for example.

It turned out recently that the notion of marked complex is equivalent to that of the later defined "discrete vector field" on a complex, for which a web search shows many publications.

See the published version

Jones, D.W. A general theory of polyhedral sets and the corresponding $T$-complexes. Dissertationes Math. (Rozprawy Mat.) 266 (1988) 110.