Detecting dependencies in geometric constraint systems

Geometric constraint systems underly popular Computer Aided Design software. Automated approaches for detecting dependencies in a design are critical for developing robust solvers and provid- ing informative user feedback, and we provide algorithms that recognize two types of dependencies. First, we give a pebble game algorithm for detecting generic dependencies. Then, we focus on identifying the “special positions” of a design in which generically independent constraints become dependent. We present combinatorial algorithms for identifying subgraphs associated to factors of a particular polynomial, whose vanishing indicates a special position and resulting dependency. Factors may allow a geometric interpretation giving conditions (e.g., “these two lines being parallel cause a dependency”) determining the special position.