Recognising polytopical cell complexes and constructing projection polyhedra

A simple cell complex C in Euclidean d-space Ed is a covering of Ed by finitely many convex j-dimensional polyhedra (the j-faces of C), each of which is in the closure of exactly d-j+1 d-faces of C. An algorithm that recognises when C is the projection of the set of faces bounding some convex polyhedron P(C) in Ed+1, and that constructs P(C) provided its existence is outlined. The method is optimal at least for d=2. No complexity results were previously known for both problems. The results have applications in statics, to the recognition of Voronoi diagrams, and to planar point-location