There are a vast number of different approaches to constraint solving, owing to the importance of the problem. We survey briefly the major approaches and characterize their advantages and shortcomings.Focusing on the graph-directed approach to constraint solving, we explain in detail how it works. A constraint solver of this type probably begins with a reduction of the shape vocabulary and of the constraints. For instance, a fixed-radius circle might be replaced with its centerpoint, suitably changing the constraints to account for the known radius. The solver then formulates a constraint graph. By a graph analysis, a sequence of computational steps is derived which, when carried out, solves the constraint problem. These steps are elementary steps and steps that merge clusters of geometric elements arising from partial constructions.
The scope of problems that can be solved in this approach can be enlarged by some graph transformations that correspond to reasoning about the constraint problem. Moreover, different solutions to a constraint problem may exist, and they can be found by a suitable mechanism that identifies any one of the potentially exponential number of different solutions. This mechanism also figures prominently in the problem of solving the constraint problem for different values of dimensional constraints, such as might arise in animation.
Variable-radius circles are circles whose radius must be determined implicitly from the constraint schema, rather than being stipulated explicitly. Such geometric elements add new complexity to the constraint solver and necessitate new construction techniques. Among these techniques are classical constructions that solve the Apollonius problem and related problems, using techniques of Laguerre geometry. We will sketch some of these techniques as well, time permitting.