TY - GEN
T1 - COMPLEXITY OF RECOGNIZING POLYHEDRAL SCENES.
AU - Kirousis, Lefteris M.
AU - Papadimitriou, Christos H.
PY - 1985
Y1 - 1985
N2 - Given a drawing of straight lines on the plane, one wishes to decide whether it is the projection of the visible part of a set of opaque polyhedra. It is shown that this problem is NP-complete, even in the relatively simple case of trihedral scenes (no four planes share a point) without shadows or cracks. Despite this negative result, a fast algorithm is obtained for the important special case of orthohedral scenes (all planes are perpendicular to one of the three axes) with a fixed number of 'possible' objects.
AB - Given a drawing of straight lines on the plane, one wishes to decide whether it is the projection of the visible part of a set of opaque polyhedra. It is shown that this problem is NP-complete, even in the relatively simple case of trihedral scenes (no four planes share a point) without shadows or cracks. Despite this negative result, a fast algorithm is obtained for the important special case of orthohedral scenes (all planes are perpendicular to one of the three axes) with a fixed number of 'possible' objects.
UR - http://www.scopus.com/inward/record.url?scp=0022231248&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0022231248&partnerID=8YFLogxK
U2 - 10.1109/sfcs.1985.59
DO - 10.1109/sfcs.1985.59
M3 - Conference contribution
AN - SCOPUS:0022231248
SN - 0818606444
SN - 9780818606441
T3 - Annual Symposium on Foundations of Computer Science (Proceedings)
SP - 175
EP - 185
BT - Annual Symposium on Foundations of Computer Science (Proceedings)
PB - IEEE
ER -