| Motivated by applications in Computer Aided Design (CAD) and biology, we investigate geometric constraint systems, composed of atomic elements with constraints between them. A well-studied model in rigidity theory is the bar-and-joint structure, where the atomic elements are universal joints connected by fixed-length bar constraints. We propose several new models involving constraints arising in CAD and biology and provide the theoretical foundation for each. In particular, we present a model addressing the pairwise constraints among points, lines and planes found in constraint-based CAD software, such as in the assembly environment of the widely-used SolidWorks CAD application.;As a result, we identify and generalize combinatorial properties that appear as necessary conditions for generic rigidity of these new constraint systems; in some cases, the conditions are also sufficient, thus providing a complete characterization. We study sparsity for graphs, arising from known rigidity results and present extensions of this concept to graded, mixed and nested sparsity. For these sparsity properties, we present algorithms that solve the fundamental questions of Decision, Extraction and Components, based on the efficient and elegant pebble games first developed for planar bar-and-joint rigidity. |
