Effectively Labeling Planar Projections of Polyhedra

Lefteris M. Kirousis

Research output: Contribution to journalArticlepeer-review


A well-known method for interpreting planar projections (images) of 3-dimensional polyhedra is to label their lines by the Clowes-Huffman scheme. However, the question of whether there is such a labeling has been shown to be NP-complete. In this paper, a linear in time algorithm is given that answers the labelability question under the assumption that some information is known about those edges of the polyhedron whose both faces are visible. In many cases, this information can be derived from the image itself. Moreover, the algorithm has an effective parallel version, i.e., with polynomially many processors it can be executed in time polynomial in log n.

Original languageEnglish (US)
Pages (from-to)123-130
Number of pages8
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Issue number2
StatePublished - Feb 1990


  • Labeling
  • polyhedron
  • two-dimensional image of a polyhedron

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics


Dive into the research topics of 'Effectively Labeling Planar Projections of Polyhedra'. Together they form a unique fingerprint.

Cite this