Empirically-derived estimates of the complexity of labeling line drawings of polyhedral scenes

摘要

Several results have been obtained in the past about the complexity of understanding line drawings of polyhedral scenes. Kirousis and Papadimitriou (1988) have shown that the problem of labeling line drawings of trihedral scenes is NP-complete. The human brain, however, seems to grasp at a glance the 3D structure associated with a line drawing. A possible explanation of this discrepancy, offered by Kirousis and Papadimitriou themselves, is that the worst-case complexity does not reflect the real difficulty of labeling line drawings, which might be far less in the average or in “typical” cases. However, no statistical analysis has ever been carried out to test this conjecture. The core of this paper is an algorithm for the generation of random instances of polyhedral scenes. Random instances of line drawings are then obtained as perspective projections of these scenes, and can be used as an input to standard labeling algorithms so as to derive experimental estimates of the complexity of these algorithms. The results indicate that the median-case complexity is linear in the number of junctions. This substantiates the conjecture that “typical” instances of line drawings are easy to label, and may help explain the ease by which the brain is able to solve the problem.