An algebraic and combinatorial approach to the analysis of line drawings of polyhedra (Q798004)

A method for judging whether a line drawing represents a polyhedral scene or not is presented. First, a necessary and sufficient condition for a line drawing to represent a polyhedral scene is given in terms of linear algebra. This is a theoretical solution to the problem, but not practical in the sense that some pictures that are intuitively correct for humans are judged to be incorrect if they contain even slight errors such as digitization errors. Next, therefore, a generic property is studied. A necessary and sufficient condition for a line drawing whose vertices are in general position to represent a polyhedral scene is presented in terms of combinatorial structures as to which vertices should be on which faces. The condition is that any substructure of the polyhedron consisting of two or more faces satisfies \(V+3F\geq R+4,\) where V, F, and R are the number of faces, and the number of incidence pairs of vertices and faces, respectively, of the substructure. The results are furthermore applied to some fundamental problems in scene analysis such as correction of vertex-position errors, recognition of unique solvability of some figure-construction problems, and classification of impossible objects.