  In this paper, we are concerned with geometric constraint solvers, i.e., with
programs that find one or more solutions of a geometric constraint problem. If
no solution exists, the solver is expected to announce that no solution has
been found. Owing to the complexity, type or difficulty of a constraint
problem, it is possible that the solver does not find a solution even though
one may exist. Thus, there may be false negatives, but there should never be
false positives. Intuitively, the ability to find solutions can be considered a
measure of solver's competence. We consider static constraint problems and
their solvers. We do not consider dynamic constraint solvers, also known as
dynamic geometry programs, in which specific geometric elements are moved,
interactively or along prescribed trajectories, while continually maintaining
all stipulated constraints. However, if we have a solver for static constraint
problems that is sufficiently fast and competent, we can build a dynamic
geometry program from it by solving the static problem for a sufficiently dense
sampling of the trajectory of the moving element(s). The work we survey has its
roots in applications, especially in mechanical computer-aided design (MCAD).
The constraint solvers used in MCAD took a quantum leap in the 1990s. These
approaches solve a geometric constraint problem by an initial, graph-based
structural analysis that extracts generic subproblems and determines how they
would combine to form a complete solution. These subproblems are then handed to
an algebraic solver that solves the specific instances of the generic
subproblems and combines them.
