The complexity of recognizing polyhedral scenes

1 January 1985

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

No. 02725428,p. 175-185
https://doi.org/10.1109/sfcs.1985.59

Abstract

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. Although there is an extensive literature and reports on empirically succesful algorithm: for this problem, there has been no definite result concerning its complexity. In this paper we show that, rather surprisingly, this problem is NP-complete. This is true even in the relatively simple case of trihedral scenes (no four planes share a point) without shadows or cracks. Despite this negative result, we present a fast algorithm 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.

Keywords

This publication has 6 references indexed in Scilit:

Mathematical Structures of Line Drawings of Polyhedrons—Toward Man-Machine Communication by Means of Line Drawings
IEEE Transactions on Pattern Analysis and Machine Intelligence, 1982
Planar Formulae and Their Uses
SIAM Journal on Computing, 1982
A theory of Origami world
Artificial Intelligence, 1980
Polynomial algorithms in linear programming
USSR Computational Mathematics and Mathematical Physics, 1980
A context sensitive line finder for recognition of polyhedra
Artificial Intelligence, 1973
On seeing things
Artificial Intelligence, 1971