Authors: Brigitte Servatius and Walter Whiteley
Reference: SIAM Journal on Discrete Mathematics, Vol. 12, No. 1, pp. 136–153 (1999)
Selected Figures:
Abstract: A {\em plane configuration} in Computer Aided Design (CAD) is a collection of geometric objects such as points, line segments and circular arcs in the plane, together with constraints on and between these objects. Naturally the designer wants to know if a realization of the configuration exists and is uniquely determined. A realization of a plane configuration is called a {\em plane design}. Beyond simple uniqueness of design, there are other fundamental design questions: If global uniqueness is not achieved, is the design locally unique? If the design permits continuous deformations, which additional constraints would give the appropriate uniqueness? Are all constraints essential in producing the design or are there constraints which are forced by the remaining ones?
Given a design, the constraints can be written as a system of algebraic equations whose variables are the coordinates and parameters of the geometric objects. Some of the above questions may be answered by computing the rank of the Jacobian of the system of constraint equations. Because of the size of the system and possible degeneracies, computation may be slow and unstable. Therefore a mathematical theory which answers these questions purely combinatorially is desirable.
The classical problem of Euclidean Construction may be stated in the language of plane designs, as well as other familiar geometric problems. Much is known about {\em length designs}, where the objects are points and the distances between certain pairs of points are prescribed, forming the familiar mathematical model for a bar and joint framework. On the other hand, {\em direction designs}, in which the constraints prescribe directions instead of distances between points, is well understood as the problem of parallel drawings. Interesting open cases include {\em geodesy} - designs involving only points, lengths and angles; and {\em projective geometry} - designs involving lines and incidences.
We will start out by summarizing results for frameworks and parallel drawings. We combine these two theories by introducing a new matroid on the edge set of the complete graph with doubled edges to describe the combinatorial properties of direction--length designs.
