An efficient parallel algorithm for geometrically characterising drawings of a class of 3-D objects

Nick D. Dendris, Iannis A. Kalafatis, Lefteris M. Kirousis

Research output: Contribution to journalArticlepeer-review


Labelling the lines of a planar line drawing of a 3-D object in a way that reflects the geometric properties of the object is a much studied problem in computer vision, considered to be an important step towards understanding the object from its 2-D drawing. Combinatorially, the labellability problem is a Constraint Satisfaction Problem and has been shown to be NP-complete even for images of polyhedral scenes. In this paper, we examine scenes that consist of a set of objects each obtained by rotating a polygon around an arbitrary axis. The objects are allowed to arbitrarily intersect or overlay. We show that for these scenes, there is a sequential lineartime labelling algorithm. Moreover, we show that the algorithm has a fast parallel version that executes in O(log3n) time on an Exclusive-Read-Exclusive-Write Parallel Random Access Machine with O(n3/log3n) processors. The algorithm not only answers the decision problem of labellability, but also produces a legal labelling, if there is one. This parallel algorithm should be contrasted with the techniques of dealing with special cases of the constraint satisfaction problem. These techniques employ an effective, but inherently sequential, relaxation procedure in order to restrict the domains of the variables.

Original languageEnglish (US)
Pages (from-to)375-387
Number of pages13
JournalJournal of Mathematical Imaging and Vision
Issue number4
StatePublished - Dec 1994


  • efficient parallel algorithms
  • image analysis
  • labelling of lines of drawings
  • line drawings
  • planar projections of 3-D objects

ASJC Scopus subject areas

  • Statistics and Probability
  • Modeling and Simulation
  • Condensed Matter Physics
  • Computer Vision and Pattern Recognition
  • Geometry and Topology
  • Applied Mathematics


Dive into the research topics of 'An efficient parallel algorithm for geometrically characterising drawings of a class of 3-D objects'. Together they form a unique fingerprint.

Cite this