Combinatorial Analysis for CAD

dc.contributorSidman, Jessica
dc.contributorSheldon, Daniel
dc.contributor.advisorSt. John, Audrey
dc.contributor.authorYu, Xilin
dc.description.abstractComputer Aided Design software allows mechanical engineers and architects to design complicated systems by specifying geometric constraints on small building blocks. One goal of CAD software is to give users feedback on whether the specified constraints are consistent or not. To approach this problem, we model a design as a body-and-cad framework, turn the framework into a primitive cad graph, and then use a combinatorial property called [a,b]-sparsity to analyze body-and-cad rigidity. We work with an efficient algorithm called the [a,b]-pebble game to check [a, b]-sparsity using Knuth‘s algorithm for matroid partitioning in the pebble game. The [a, b]-pebble game additionally finds [a,b]-circuits which indicate minimal inconsistencies in the constraints. A categorization of the structures of these circuits can help in giving more intuitive feedback to CAD users. This thesis studies the structures of circuits from a combinatorial perspective. Three categories of circuits were identified previously, but it remained open if the categorization was complete. By systematic enumeration of [a,b]-sparse graphs, we find circuits not in the known categories. We present both statistical results on the enumeration and categorization of [a, b]-circuits and case studies on selected uncategorized circuits. We also offer theoretical analysis on the relationship between the structures of circuits and properties of an associated graph called the Knuth graph.en_US
dc.description.sponsorshipComputer Scienceen_US
dc.subjectMatroidal circuiten_US
dc.subjectCombinatorial Analysisen_US
dc.subjectComputer Scienceen_US
dc.titleCombinatorial Analysis for CADen_US
mhc.institutionMount Holyoke College


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
570.42 KB
Adobe Portable Document Format