Detecting dependencies in geometric constraint systems

Authors: James Farre, Helena Kleinschmidt, Jessica Sidman, Audrey Lee-St. John, Stephanie Stark, and Louis Theran
Proc. of: Automated Deduction in Geometry ADG’14, 2014.
Full text: URL

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.