The complexity of recognizing polyhedral scenes

Given a drawing of straight lines on the plane, we wish to decide whether it is the projection of the visible part of a set of opaque polyhedra. This is the fundamental algorithmic problem that underlies much of the research in computer vision. Although there are extensive literature and reports on empirically successful algorithms for this problem and its many extensions, there has been no definite result concerning its complexity. In this paper we show that, rather surprisingly, this problem is NP-complete, and therefore there is probably no polynomial-time algorithm for solving it. This is true even in the relatively simple case of trihedral scenes (no four planes share a point) without shadows and cracks. Despite this negative result, we present positive results for the important special case of orthohedral scenes (all planes are normal to one of the three axes).