Recognizing polytopical cell complexes and constructing projection polyhedra

F. Aurenhammer

Abstract:

A simple cell complex $C$ in Euclidean $d$-space $E^d$ is a covering of $E^d$ 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 $E^{d+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.



Reference: F. Aurenhammer. Recognizing polytopical cell complexes and constructing projection polyhedra. Journal of Symbolic Computation, 3(3):249-255, 1987. [IIG-Report-Series 203, TU Graz, Austria, 1985].