The complexity of recognizing polyhedral scenes

Lefteris M. Kirousis, Christos H. Papadimitriou

Research output: Contribution to journalArticlepeer-review


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).

Original languageEnglish (US)
Pages (from-to)14-38
Number of pages25
JournalJournal of Computer and System Sciences
Issue number1
StatePublished - Aug 1988

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'The complexity of recognizing polyhedral scenes'. Together they form a unique fingerprint.

Cite this