Geometric Constraint Solving (I) Graph-Directed Solvers

Christoph M. Hoffmann Computer Science Department Purdue University West Lafayette, IN 47907-1398 (USA) cmh@cs.purdue.edu

Abstract

Geometric constraint systems arise in geometric modeling applications as a means for expressing conveniently the design of three-dimensional shapes. The two most important problem classes are for 2-dimensional and for 3dimensional configuration. We concentrate on the 2-dimensional problem only. The class of graph-directed solvers analyzes a constraint graph whose edges are the constraints and whose vertices are the geometric elements of the constraint problem. After analyzing the graph, a solution can be constructed by a sequence of construction steps and merging operations. For a large and interesting class of geometric constraint problems, a solution can be constructed in worst-case time proportional to the square of the geometric elements involved. From an algebraic point of view, graph-directed solvers decompose a system of nonlinear equations into small subsystems whose structure is known a-priori. In part, the decomposition can be thought of as standard algebraic computation, but there are also additional steps involved that do not seem to have a counterpart in symbolic algebraic computation. In particular, smaller subsystems are at some point combined using derived constraints that are formulated from the partial solution instance rather than, more generally, by general derivation. In addition to being very efficient, graph-directed solvers are capable of constructing all possible solutions of the underlying system of algebraic equations. To do so, the construction sequence is partially retraced, and at some construction step(s) different solutions of the subsystem are used. This amounts to a traversal of a tree of solutions, and is, of course, proportional in time to the size of the tree.

keywords: geometric constraints, graph-directed solvers, algebraic solvers, constraint graphs, construction steps, recursive extension and open issues