"Geometric Constraint Solving (II) Algebraic Issues" Christoph M. Hoffmann cmh@cs.purdue.edu In the simplest case, a graph-directed solver discovers that the constraint problem can be solved by a sequence of construction steps in which, at each step, a single geometric element is placed with respect to the geometric elements already so constructed. Algebraically, this situation corresponds to a block-triangular system of equations, where each block has a simple structure, consisting usually of two quadratic equations. Such constraint problems can be solved in linear time. In the more general situation, there are three clusters of geometric elements that must be combined. Each cluster consists of three or more geometric elements that are already placed correctly with respect to each other, but whose position and orientation as rigid body in the plane is not yet known. To place them, in the simplest situation, a subset of three geometric elements is identified and constraints between them are derived from the partial solution. Then, the subset of elements is constructed in the usual way, and from the result the required rigid-body motion derived that places the three clusters into correct position relative to each other. This curious operation of merging clusters based on derived constraints is a key component of the solver. It can be thought of as instance elimination of variables, not in the symbolic algebraic sense, but in the specific sense of the partial solution known at that time. This operation should be examined closely from an algebraic perspective and properly generalized, for it could play an important role in speeding up solvers for systems of polynomial equations.