ABSTRACT
This chapter is concerned with geometric constraint solvers, that is with programs that find one or more solutions of a geometric constraint problem. A geometric constraint problem, also known as a geometric constraint system, consists of a finite set of geometric objects, such as points, lines, circles, planes, spheres, etc., and constraints upon them, such as incidence, distance, tangency, and so on. Given a geometric constraint systems (GCS), the chapter analyzes the structure of the corresponding equation system, and seek to identify smaller subsystems that can be solved independently and that admit especially efficient solution algorithms. It investigates how the structure of the constraint graph reflects the structure of the equation system that corresponds to the GCS. A GCS is well-constrained if the associated equation system has one or more discrete real solutions. GCS that are not serializable have been called variational constraint problems in some of the application-oriented literature.
