loading...
Effectively Labeling Planar Projections of Polyhedra
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/34.44400February 1990 (vol. 12 no. 2) pp. 123-130
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
L.M. Kirousis, "Effectively Labeling Planar Projections of Polyhedra," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 12, no. 2, pp. 123-130, February, 1990.
 
 
BibTex
x
 
@article{ 10.1109/34.44400,
author = {L.M. Kirousis},
title = {Effectively Labeling Planar Projections of Polyhedra},
journal ={IEEE Transactions on Pattern Analysis and Machine Intelligence},
volume = {12},
number = {2},
issn = {0162-8828},
year = {1990},
pages = {123-130},
doi = {http://doi.ieeecomputersociety.org/10.1109/34.44400},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Pattern Analysis and Machine Intelligence
TI - Effectively Labeling Planar Projections of Polyhedra
IS - 2
SN - 0162-8828
SP123
EP130
EPD - 123-130
A1 - L.M. Kirousis,
PY - 1990
KW - 3D polyhedra; planar projections labelling; computerised picture processing; computerised pattern recognition; Clowes-Huffman scheme; linear-in-time algorithm; labelability; time polynomial; computational complexity; computational geometry; computerised pattern recognition; computerised picture processing; polynomials
VL - 12
JA - IEEE Transactions on Pattern Analysis and Machine Intelligence
ER -
 

A well-known method for interpreting planar projections (images) of three-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. 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 both of whose 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.

[1] 123M. B. Clowes, "On seeing things,"Artificial Intell., vol. 2, pp. 79- 116, 1971.
[2] E. F. Freuder, "On the knowledge required to label a picture graph,"Artificial Intell., vol. 15, pp. 1-17, 1980.
[3] D. A. Huffman, "Impossible objects as nonsense sentences," inMachine Intelligence, vol. 6, B. Meltzer and D. Michie, Eds. Edinburgh, Scotland: Edinburgh University Press, 1971, pp. 295-323.
[4] L. M. Kirousis and C. H. Papadimitriou, "The complexity of recognizing polyhedral scenes,"J. Comput. Syst. Sci., vol. 37, pp. 14-38, 1988.
[5] C. H. Papadimitriou, personal communication, 1985.
[6] M. J. Quinn and N. Deo, "Parallel graph algorithms,"ACM Comput. Surveys, vol. 16, pp. 319-348, Sept. 1984.
[7] K. Sugihara, "Mathematical structures of line drawings of polyhedrons--Towards man-machine communication by means of line drawings,"IEEE Trans. Pattern Anal. Machine Intell., vol. 4, pp. 458- 469, 1982.
[8] D. Waltz, "Understanding line drawings of scenes with shadows," inThe Psychology of Computer Vision, P. H. Winston, Ed. New York: McGraw-Hill, 1975, pp. 19-91.
[9] P. M. Winston,Artificial Intelligence. Reading, MA: Addison-Wesley, 1984.

Index Terms:
3D polyhedra; planar projections labelling; computerised picture processing; computerised pattern recognition; Clowes-Huffman scheme; linear-in-time algorithm; labelability; time polynomial; computational complexity; computational geometry; computerised pattern recognition; computerised picture processing; polynomials
Citation:
L.M. Kirousis, "Effectively Labeling Planar Projections of Polyhedra," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 12, no. 2, pp. 123-130, Feb. 1990, doi:10.1109/34.44400
Usage of this product signifies your acceptance of the Terms of Use.