The computer interpretation of line drawings is a classic problem in arti'cial intelligence (AI) which has inspired the development of some fundamental AI tools, including constraint propagation, probabilistic relaxation, the characte- zation of tractable constraint classes and, most recently, the propagationof soft constraintsin'nite-domainoptimizationproblems. Line drawinginterpretation has many distinct applications on the borderline of computer...