Recognizing polytopical cell complexes and constructing projection
A simple cell complex
is a covering of
by finitely many convex
-dimensional polyhedra (the
each of which is in the closure of exactly
algorithm that recognises when
is the projection of the set of faces
bounding some convex polyhedron
, and that constructs
provided its existence is outlined. The method is optimal at least for
. 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].