Geometric constraint subsets and subgraphs in the analysis of assemblies and mechanisms

Geometric Reasoning ability is central to many applications in CAD/CAM/CAPP environments -- An increasing demand exists for Geometric Reasoning systems which evaluate the feasibility of virtual scenes specified by geometric relations -- Thus, the Geometric Constraint Satisfaction or Scene Feasibility (GCS/SF) problem consists of a basic scenario containing geometric entities, whose context is used to propose constraining relations among still undefined entities -- If the constraint specification is consistent, the answer of the problem is one of finitely or infinitely many solution scenarios satisfying the prescribed constraints -- Otherwise, a diagnostic of inconsistency is expected -- The three main approaches used for this problem are numerical, procedural or operational and mathematical -- Numerical and procedural approaches answer only part of the problem, and are not complete in the sense that a failure to provide an answer does not preclude the existence of one -- The mathematical approach previously presented by the authors describes the problem using a set of polynomial equations -- The common roots to this set of polynomials characterizes the solution space for such a problem -- That work presents the use of Groebner basis techniques for verifying the consistency of the constraints -- It also integrates subgroups of the Special Euclidean Group of Displacements SE(3) in the problem formulation to exploit the structure implied by geometric relations -- Although theoretically sound, these techniques require large amounts of computing resources -- This work proposes Divide-and-Conquer techniques applied to local GCS/SF subproblems to identify strongly constrained clusters of geometric entities -- The identification and preprocessing of these clusters generally reduces the effort required in solving the overall problem -- Cluster identification can be related to identifying short cycles in the Spatial Con straint graph for the GCS/SF problem -- Their preprocessing uses the aforementioned Algebraic Geometry and Group theoretical techniques on the local GCS/SF problems that correspond to these cycles -- Besides improving theefficiency of the solution approach, the Divide-and-Conquer techniques capture the physical essence of the problem -- This is illustrated by applying the discussed techniques to the analysis of the degrees of freedom of mechanism