Manifolds and Configuration Spaces

By a theorem of Kapovich and Milson [KM], for every smooth compact manifold M there is a linkage with configuration space homeomorphic to N copies of M for a natural number N. The proof is based on theorem by J. Nash [N] and A. Tognoli [T] stating that  such a manifold M is homeomorphic to the zero set of a real polynomial function f (x1,...,xn) (all points: (x1,...,xn)eRn, f(x1,...,xn)=0). In this page we shall give an outline of Kapovich and Milson's proof which utilizes functional linkages.

The natural input domain of functional linkages is the complex plane, however from now on we will only be interested in real polynomial functions. Therefore we will need to restrict the input domain of linkages we construct from the complex plane to the real axis. This is achieved by attaching a Peacullier's Linkage to every input joint of the desired linkage, such that the motion of each input joint is restricted to a wide enough segment of the real axis.

Now for a given real polynomial function f we know how to construct a functional linkage L', which can compute f on an open input domain, such that the input domain contains the zero set of f. Finally we anchor the output joint of L' to the origin (0,0) to end with a new linkage L, the positions of the input joints of L are exactly the zero set of f. However this does not prove that the configuration space of L is homeomorphic to the zero set of f, since the positions of the input joints do not usually determine the positions of some of the other joints in the linkage L. The positons of the input joints of L determine the positions of all  input or output joints of the basic linkages constructing L, but all other supporting joints can take 2 positions (in regular cases). However, as the zero set is contained inside the input domain of L, no two adjacent bars connected by a supporting joint of L can stretch-out:  stretched.gif (1119 bytes) therefore if we start from a given state of L no supporting joint can switch bends along any possible motion of L. By modifying the basic linkages for translation, inversion, Peacullier's Linkage and scalar multiplying. Kapovich and Milson proved that the position of the input joints and an initial state of L determine the state of L, and thus proved the theorem. We will examine the basic linkages and show how to modify them such that the linkage L would be appropriate.

Basically the states we would like to avoid are those in which the linkage fails to describe its proposed polynomial function. The first type of invalid states occur when two adjacent bars of same length are placed on each other, this allows the joint connecting the bars to freely rotate on a circle, instead of the only 2 possible positions in regular cases. The right image displays a state of the Peacullier's Linkage in which Joint A can rotate freely around the center O.

degenerate.gif (2980 bytes)

Peacullier's Linkage with 2 joints placed on a single point O (shown slightly apart)

The next type of states we would like to eliminate are the supplementary states of the functional linkage, in the right image an  additional position of the input joint is shown. Although this is a possible state of the Translator Linkage, it does not correspond to the designated computation of the linkage.

additionstate.gif (9459 bytes)

Translator Linkage with an additional position of the input joint.

Kapovich and Milson's modifications

Translator Linkage.

translator.gif (1703 bytes)

AC || HI, CE || IG, a>b

First we avoid the position where the input joint is placed on the anchor by setting different heights a, b to the 2 parallelograms constructing the linkage (first type of invalid states).  This limits the input domain of the linkage to the annulus: 0<|a-b|<||E-A||<a+b , since we can set the anchor at any point in the plane and select any different values for a and b we can compute translation on any restricted area of the plane. Next we avoid positions in which the joints ABDC and CDFE do not form parallelograms (second type of invalid states), by connecting an additional bar to the centers of AB and CD and an additional bar to the centers of EF and CD this process is called:  "rigidifying a square".

Pantograph linkage

Scalar Multiplier for a>1 the anchor is placed at (0,0)

pantograph.gif (1852 bytes)

aAD = AF, aEF = CF, 
aAB = AC

First we rigidify the square DBEF as in the previous linkage. Next  we avoid positions  in which the input joint (or output joint) is placed on the origin by setting different lengths to AD and FE. this limits the input to an annulus around the origin and removes a circle around the origin from any possible input domain. if we need to compute scalar multiplication around  the origin we construct  a new linkage by composing linkages by the equation aX = a(X-b)+ab, by choosing a large enough b>0. Similiary for the Adder Linkage if  addition should be computed around equal inputs (B=C) we construct a new Linkage to compute the average: using the equation (B+C)/2 = [(B+b)+(C-b)]/2


The rigidifying bars have been removed from the linkages in the above applet

Inversor Linkage and Peacullier's Linkage

inversion.gif (2443 bytes)


Again we rigidify the square BECD. Next we avoid positions where joints D, E  are placed on the same point by adding two bars with different lengths as in the image above. Although this limits  the input domain, by selecting a large enough lengths for AD and BE the input domain can contain the annulus r -1 <||input||<r for a given r>1. Similarly the Peacullier's Linkage would contain a large segment of the real line for an appropriate choices for AD and BE.

Back to Homepage