Detecting dependencies in geometric constraint systems

Authors: James Farre, Helena Kleinschmidt, Jessica Sidman, Audrey Lee-St. John, Stephanie Stark, Louis Theran, and Xilin Yu
Journal: Computer Aided Geometric Design, 2016.
Full text: DOI

Automated approaches for detecting dependencies in structures created with Computer Aided Design software are critical for developing robust solvers and providing informative user feedback. We model a set of geometric constraints with a bi-colored multigraph and give a graph-based pebble game algorithm that allows us to determine combinatorially if there are generic dependencies. We further use the pebble game to yield a decomposition of the graph into factor graphs which may be used to give a user detailed feedback about dependent substructures in a specific realization of a system of CAD constraints with non-generic properties.