Recognising polytopical cell complexes and constructing projection polyhedra (Q1096404): Difference between revisions

A cell complex \(C\) in Euclidean \(d\)-space \(E^d\) is a face-to-face partition of \(E^d\) into finitely many convex \(j\)-dimensional polyhedra, called the \(j\)-faces of \(C\). The problems of deciding whether \(C\) is the vertical projection of the set of faces bounding a convex polyhedron \(P(C)\) in \(E^{d+1}\), resp. of reconstructing \(P(C)\) in case of its existence, are of interest in various applications. No efficient algorithms are known for general cell complexes. We present an algorithm for both problems that works in the case where the underlying cell complex \(C\) is simple, i.e., each \(j\)-face of \(C\) is in the closure of exactly \(d-j+1\) \(d\)-faces of \(C\). The method is based on the geometrical concept of the so-called orthogonal dual of \(C\) (which is of interest in its own right) and requires time proportional to the number of faces \(((d-1)\)-faces) of \(C\). This is optimal at least for \(d=2\). Beside of the obvious use of the results in scene analysis we discuss applications in statistics, to planar point location, an to the recognition of Voronoi diagrams.