Decomposition plans for geometric constraint systems

We systematically design two new decomposition–recombination (DR) planners, geared to perform well with respect to several performance measures. The DR-planning problem and the performance measures were formally defined in Part I of this paper to closely reflect specific requirements of CAD/CAM applications. As expected, in analysis and comparison based on all of these performance measures, one of the new DR-planners, the modified frontier algorithm (MFA), represents a significant improvement over existing planners based on SR (constraint shape recognition) and MM (maximum matching) that were analyzed in Part I. We also present salient heuristics and data structures used in the implementation of MFA. c ○ 2001 Academic Press 1. Preliminaries We present two decomposition–recombination (DR) planning algorithms or DR-planners, a notion that was formally defined in Part I (Section 3) of this paper. The new planners follow the overall structural description of a typical DR-planner, based on the DR-solver S given in Part I (Section 1). Furthermore, the new DR-planners adopt and adapt features of older decomposition methods such as SR (shape recognition) and MM (generalized maximum matching) that were analyzed and compared in Part I (Section 4). In particular, those methods as well as the new planners are based on degree of freedom analysis of geometric constraint hypergraphs—these concepts are reviewed in Part I (Sectio