Decomposition plans for geometric constraint systems, part I: Performance measures for CAD

A central issue in dealing with geometric constraint systems for CAD/CAM/CA E is the generation of an optimal decomposition plan that not only aids eff icient solution, but also captures design intent and supports conceptual de sign. Though complex, this issue has evolved and crystallized over the past few years, permitting us to take the next important step: in this paper, w e formalize, motivate and explain the decomposition-recombination (DR)-plan ning problem as well as several performance measures by which DR-planning a lgorithms can be analyzed and compared. These measures include: generality, validity, completeness, Church-Rosser property, complexity best- and worst -choice approximation factors, (strict) solvability preservation, ability t o deal with underconstrained systems, and ability to incorporate conceptual design decompositions specified by the designer. The problem and several o f the performance measures are formally defined here for the first time-the y closely reflect specific requirements of CAD/CAM applications. The clear formulation of the problem and performance measures allow us to p recisely analyze and compare existing DR-planners that use two well-known t ypes of decomposition methods: SR (constraint shape recognition) and MM (ge neralized maximum matching) on constraint graphs. This analysis additionall y serves to illustrate and provide intuitive substance to the newly formali zed measures. In Part II of this article, we use the new performance measures to guide th e development of a new DR-planning algorithm which excels with respect to t hese performance measures. (C) 2001 Academic Press.