TY - GEN
T1 - An efficient parallel algorithm for geometrically characterising drawings of a class of 3-D objects
AU - Dendfis, Nick D.
AU - Kalafatis, Iannis A.
AU - Kirousis, Lefteris M.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1992.
PY - 1992
Y1 - 1992
N2 - Labelling the lines of a planar line drawing ofa 3-D object in a way that reflects the geometric properties of the object is a much studied problem in computer vision and considered to be an important step towards understanding the object from its 2-D drawing. Combinatorially, the iabellability problem is a restricted version of the 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 linear-time labelling algorithm. Moreover, we show that the algorithm has a fast parallel version that executes in O(log4n) time on a EREW PRAM with O(n3/log2n) 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 sarisfaction problem. These techniques employ an effective, but inherently sequential, relaxation procedure in order to restrict the domains of the variables.
AB - Labelling the lines of a planar line drawing ofa 3-D object in a way that reflects the geometric properties of the object is a much studied problem in computer vision and considered to be an important step towards understanding the object from its 2-D drawing. Combinatorially, the iabellability problem is a restricted version of the 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 linear-time labelling algorithm. Moreover, we show that the algorithm has a fast parallel version that executes in O(log4n) time on a EREW PRAM with O(n3/log2n) 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 sarisfaction problem. These techniques employ an effective, but inherently sequential, relaxation procedure in order to restrict the domains of the variables.
UR - http://www.scopus.com/inward/record.url?scp=85029756486&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85029756486&partnerID=8YFLogxK
U2 - 10.1007/3-540-56279-6_73
DO - 10.1007/3-540-56279-6_73
M3 - Conference contribution
AN - SCOPUS:85029756486
SN - 9783540562795
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 198
EP - 208
BT - Algorithms and Computation - 3rd International Symposium, ISAAC 1992, Proceedings
A2 - Nishizeki, Takao
A2 - Ibaraki, Toshihide
A2 - Iwama, Kazuo
A2 - Yamashita, Masafurni
A2 - Inagaki, Yasuyoshi
PB - Springer Verlag
T2 - 3rd International Symposium on Algorithms and Computation, ISAAC 1992
Y2 - 16 December 1992 through 18 December 1992
ER -