Pictures as boolean formulas: A method for recognizing polyhedral scenes

摘要

Both labellability and realizability problems of planar projections of polyhedra (i.e.; pictures) are known to be NP-complete problems. This is true, even in the case of trihedral polyhedra, where exactly three faces meet at every vertex. In this paper, we examine pictures that are taken to be projections of trihedral polyhedra without holes, and contain the projections of all edges (hidden and visible) of a polyhedron. In other words, we examine pictures which represent the entire shape of a trihedral polyhedron without holes. Such a picture is a connected graph P=(V,E) with |E| edges and |V| nodes, each of degree 3 (|E| = rac{3|V|}{2}). We propose a mathematical scheme that constructs from the picture a Boolean formula Φ P, which is a conjunction of clauses, each consisting of at most two literals. Based on the satisfiability of Φ P, we show that both labellability and realizability problems can be solved efficiently in polynomial time. The category of pictures with hidden lines consists of the first category of pictures, where the labellability problem is solved in polynomial time, and, moreover, its solution implies the solution of the realizability problem in polynomial time too. Our approach may also prove useful in other applications of scene analysis.