THE COMPLEXITY OF RECOGNIZING POLYHEDRAL SCENES Extended Abstract
Lefteris M. Kirousis, Christos H. Papadimitriou · Foundations of Computer Science · 1985
Given a dr,awi ngof straight lines on the plane, we wish to decide whether it is the projection of the visible part of a set of opaque polyhedra. Although there is an extensive literature and reports on e~iri~11y succesful algorithms for this problem, there has been no definite result concerning its complex; ty. In thi s paper we show that, ratfle~ . surprisingly, this problem is NP-complete. TfllS 1S true even in the relatively simple case of trihedral scenes (no four planes share a point) without shadows or crack.s. Desp . jte this negative result, weoresent a fast algorlthm for the 1mportant spec1a~ case.of·orthohedral scenes (all planes are perpendicular to'one of the three axes) with a fixed number of possible objects.