And yet it moves: Paradoxically moving linkages in kinematics

Abstract

The possible configurations of a mechanical linkage correspond to the solutions of a system of algebraic equations. We can estimate the dimension of the solution set by counting free parameters and equational constraints. But this estimate does not always give the correct answer: sometimes the linkage moves although it should not. In this paper, we give mathematical explanations for this unexpected mobility.

Look at Figure 1: you see a mechanism that is able to draw an ellipse. If you press gently on the blue bar (connected to the right endpoint of the grey segment which is fixed), then the whole vehicle will start to move and bounce so that the red point traces the ellipse. Historically, it was a famous challenge in the 19th-century to find a mechanism that draws a straight line segment. Mathematicians even tried to prove the nonexistence of an exact solution. But then the French engineer Peaucellier and the Russian mathematician Lipkin independently found an exact solution. Starting from the mechanism in Figure 1, we can do the same thing as well (even though this was not the solution of Peaucellier/Lipkin): you can change some of the lengths so that the ellipse degenerates into a line segment traced twice in a full round.

Kempe’s universality theorem

A few years after the invention of the “straight line mechanism” by Peaucellier and Lipkin, Kempe 31 proved that every plane algebraic curve can be drawn by a mechanism moving with one degree of freedom! His construction uses the implicit equation of the algebraic curve, and the linkage draws a bounded subset of the curve. Kempe himself admits that the mechanisms constructed by his general construction are quite complicated. One of the objectives in this article is to explain how to construct a mechanism that draws a given rational curve, i.e., a curve that it is given by a parametrization by rational functions. Compared with Kempe, this construction gives simpler results when it applies (not every algebraic curve is rational).

Unexpected mobility

Most of the mechanisms in this paper will be paradoxical, in the following sense: by a systematic counting of degrees of freedom and constraints, one can estimate if a given mechanism moves. For a paradoxical mechanism, this estimate predicts that the mechanism is rigid: there are sufficiently many constraints so that there should be no freedom left for motion, except moving the mechanism as a whole like a rigid body. Still, the mechanism does move nontrivially. We discuss five mathematical tools that somehow “explain” the unexpected mobility:

•

edge colorings of graphs;

•

factorization of polynomials over skew coefficient rings;

•

symmetry as a rule changer for counting variables and constraints;

•

a projective duality relating a set of relative positions to a set of geometric parameters;

•

compactification, i.e., a closer analysis of “limit configurations at infinity”.

Links and joints

We need to introduce a few concepts from kinematics (please do not worry, we will keep the amount of definitions at a minimal level). A linkage (or mechanism) in 3-space is composed of rigid bodies called links (or bars, rods) that are connected by joints (e.g., hinges or spherical joints); examples occur in mechanical engineering and robotics, but also in sports medicine—the human skeleton may be considered as a quite complex linkage—and in chemistry, at a microscopic scale. If two links are connected by a joint, then the type of joint determines a set of possible relative positions of one link with respect to the other. A revolute joint (or R-joint or hinge) allows a one-dimensional set of rotations around an axis which is fixed in both links; this set is a copy of $\mathrm{SO}_2$. This type of joint appears most frequently, for example, in doors and windows or in connection with wheels (see also Figure 2, left). A spherical joint (or S-joint) allows a three-dimensional set of rotations around a point which is fixed in both links; this set of motions is a copy of $\mathrm{SO}_3$. An example is the hip joint of the human skeleton (see Figure 2, middle). And a prismatic joint (or P-joint) allows a one-dimensional set of translations in a fixed direction; this set is theoretically a copy of $\mathbb{R}$, but in reality, it is a bounded interval. Teachers and students in mathematics often operate such a joint when moving a blackboard up and down (see Figure 2, right, for a different example).

Configurations

If two links are not directly connected by a joint, then the set of possible relative positions of one with respect to the other is determined by other links and joints forming chains that connect the two given links. In general, the description is more complicated, and it is one of the main tasks of kinematics to determine these sets. In any case, they are subsets of the group $\mathrm{SE}_3$ of direct isometries, also known as Euclidean displacements. The set of all possible relative positions of any pair of rigid bodies of a linkage $L$ is called the configuration space of $L$. For the type of joints mentioned above (revolute, spherical, and prismatic), it is possible to express the constraints coming from the joints by algebraic equations in the joint parameters. Therefore, the configuration space is an algebraic variety. Its dimension is called the mobility of $L$.

A linkage is given by combinatorial data, namely the graph indicating which rigid bodies are connected by joints and the type of joints such as revolute, spherical, prismatic; and by geometric parameters determining the fixed position of the joint axis in each of the two links attached to any R-joint and the fixed position of the anchor point in each of the two links attached to any S-joint. The computation of the configuration space of a given linkage can be reduced to solving a system of algebraic equations with parameters, with the size of the system determined by the combinatorics. These systems form a rich source of computational problems in computer algebra and polynomial system solving (see 45 and the references cited there).

Structure of the paper

The paper has six sections. In Section 1, we discuss combinatorial methods for estimating the dimension of the configuration space, based on counting variables and equational conditions; this is necessary to make precise what “paradoxical” means. Section 2 deals with planar linkages whose links are line segments joined by revolute joints, also known as moving graphs; we discuss graphs that should be rigid but actually move. Section 3 deals with spatial linkages in the plane with revolute joints, and uses dual quaternions to construct examples of simply closed linkages that are paradoxically movable. Section 4 deals with symmetries and explains how they can change the counting rules. Section 5 deals with a particular type of linkage called multipods or Gough–Stewart platforms; here, projective duality is a powerful mathematical tool that allows us to construct paradoxical examples. Section 6 is concerned with the problem of finding necessary conditions for mobility, based on the idea of analyzing the “configurations at infinity” of a mobile linkage. In the three subsections of Section 6, moving graphs, simply closed loops with revolute joints, and multipods are revisited from the point of view of what happens at infinity.

1. Predicting mobility

Given the combinatorics of a linkage, i.e., the number of its rigid bodies and which of them are connected by joints, it is possible to estimate the mobility by counting free variables and equational constraints. In kinematics, this is called the Chebychev/Grübler/Kutzbach (CGK) formula. In structural rigidity, this is called Maxwell’s rule.

Moving graphs

In this section, we start with the two-dimensional situation. Every link is a line segment in the plane $\mathbb{R}^2$. In the plane, it does not make sense to distinguish revolute joints and spherical joints, and we do not consider prismatic joints. The combinatorics of the linkage is conveniently described by a graph $G=(V,E)$, with vertices corresponding to joints and edges corresponding to links. If a line segment has three or more (say $k$) joints connecting to other links, then we split it up into several edges: we get $k$ vertices corresponding to joints and we connect them in all possible ways by ${k\choose 2}$ edges. For instance, the green link in Figure 1 will correspond to a triangle in the graph, which is geometrically degenerate because its three vertices are collinear. We assume that the linkage has no dangling links, i.e., no vertices of degree 1, because they would rotate freely around the connected vertex.

For a graph $G=(V,E)$, an edge length assignment is a vector $\lambda \in \mathbb{R}^E$ indexed by the edges with positive real coordinates $\lambda _e$ for all $e\in E$. A configuration of $(V,E,\lambda )$ is a collection $(\rho _v)_{v\in V}$ with $\rho _v\in \mathbb{R}^2$, such that for any edge $e=(u,v)$, we have $||\rho _u-\rho _v||=\lambda _e$. Two configurations $\rho ,\rho '$ are equivalent if there is a direct isometry $\sigma :\mathbb{R}^2\to \mathbb{R}^2$ of the plane such that $\sigma (\rho _v)=\rho '_v$ for all $v$. If we choose two vertices $v,w\in V$ such that $\rho _v\ne \rho _w$, then there is a unique representative $\rho '$ in the equivalence class of $\rho$ such that $\rho _v=(0,0)$ and $\rho _w=(0,c)$ for some $c>0$; we then say that $\rho '$ is a normalized configuration.

Remark 1.1.

In rigidity theory, one often defines two configurations to be equivalent if there is an isometry of the plane taking the points of the first configuration to the points of the second configuration—in other words, configurations obtained by reflections are equivalent. For questions on rigidity, it is not important whether we factor out the group of $\mathrm{SE}_2$ of direct isometries or the group ${\mathrm{E}}_2$ of direct and indirect isometries.

For a given graph $G=(V,E)$ with edge length assignment $\lambda$, its normalized configurations are the solutions of a system of algebraic equations of the form

$$\begin{equation*} (x_a-x_b)^2+(y_a-y_b)^2 = \lambda _{ab}^2 \end{equation*}$$

for each edge $\{a,b\}\in E$, and the normalization conditions

$$\begin{equation*} x_v=y_v=x_w=0,\quad y_w>0 . \end{equation*}$$

The number of nonzero variables is $2|V|-3$, and the number of equations is $|E|$. We leave out the inequality, because it is inessential for the dimension count. The number $\max (0,2|V|-3-|E|)$ is called the CGK estimate; it is an estimate for the dimension of the set of equivalence classes of configurations. In kinematics, this dimension is called the mobility of the linkage. If the dimension is zero, then the linkage is rigid; if it is zero, then the linkage is mobile.

Figure 3.

Two planar linkages with six joints and nine links with the same underlying graph. The left one is rigid, the right one is mobile.

Generic mobility

For a concrete instance, the CGK estimate comes without any warranties. However, we can say something definite for the generic case. Here we use the word “generic” in the following sense. Assume that a certain statement depends on instances parametrized by an open subset $P$ of a vector space (in our case, instances are in $\mathbb{R}^E$). Then we say that the statement is generically true if the subset of instances such that the statement is false is contained in an algebraic subvariety of $P$ of strictly smaller dimension.

Proposition 1.2.

Let $G=(V,E)$ be a graph. Let $\lambda \in \mathbb{R}^E$ be a generic length assignment. Let $X_\lambda \in \mathbb{R}^{2|V|-3}$ be set of normalized configurations of $(V,E,\lambda )$. If $2|V|-3-|E|\ge 0$, then $X_\lambda$ is either empty or a real manifold of dimension $2|V|-3-|E|$. In particular, if $2|V|-3-|E|= 0$, then a generic length assignment allows only finitely many normalized configurations.

Proof.

Let $f:\mathbb{R}^{2|V|-3}\to \mathbb{R}^{|E|}$ be the map

$$\begin{equation*} (x_a,y_a)_{a\in V}\mapsto ((x_a-x_b)^2+(y_a-y_b)^2)_{\{a,b\}\in E} \end{equation*}$$

(in the domain, remove the three coordinates known to be zero). This is a differential map, which assigns to each normalized configuration of points in $\mathbb{R}^2$ the square of the lengths of edges. Therefore $X_\lambda = f^{-1}(\lambda )$.

If the image of $f$ does not contain an open neighborhood of $\lambda$, then it also does not contain $\lambda$ because $\lambda$ is chosen generically. Hence $X_\lambda$ is empty and there is nothing left to prove.

Otherwise, let $U$ be an open neighborhood of $\lambda$ and apply Sard’s theorem to the map $f|_{f^{-1}(U)}$. It implies that the set of critical values does not contain $\lambda$. Hence the Jacobian of $f$ has rank $E$ at every point of $f^{-1}(U)$, and this shows the claim.

■

Generic rigidity

If $|E|=2|V|-3$, then two cases are possible: either the image of the map $f:\mathbb{R}^{2|V|-3}\to \mathbb{R}^{|E|}$ in the proof contains an open subset, or the image of the map is contained in a subset of lower dimension. In the first case, the graph is rigid: a generic configuration cannot move continuously, by Proposition 1.2. In the second case, a generic length assignment does not have any configuration. The following theorem determines which of the two cases holds.

Theorem 1.3.

Let $G=(V,E)$ be a graph such that $|E|=2|V|-3$. Then there is an open set of edge assignments $\lambda$ with a finite and positive number of configurations if and only if $|E'|\le 2|V'|-3$ for every subgraph $G'=(V',E')$ of $G$.

This theorem was proved by Pollaczek-Geiringer 39 and rediscovered 40 years later by Laman 32 (formulated as a criterion for the statement on a given graph that the $f$-image of a generic point defines a rigid length assignment). The graphs that satisfy the necessary and sufficient condition above are called Laman graphs. Here is the proof for the necessity: if there is a subgraph $G'=(V',E')$ with $|E'|> 2|V'|-3$, then the algebraic system describing normalized configurations of the subgraph is overdetermined. So, for generic edge length assignments, there is no configuration for the subgraph, and therefore also no configuration for the graph $G$ itself.

In dimension 3, the CGK estimate for the mobility of a graph $G=(V,E)$ is equal to $3|V|-6-|E|$. Proposition 1.2 holds with that bound: if $\lambda \in \mathbb{R}^{|E|}$ is a generic edge assignment, and the normalized configuration space $X_\lambda$ is not empty, then it has dimension $3|V|-6-|E|$. The condition $|E'|\le 3|V'|-6$ for every subgraph $(V',E')$ is still necessary for the statement that $X_\lambda$ is generically not empty, but it is not sufficient: Figure 4 shows the “double banana”, a graph with eight vertices and 18 edges, such that a generic assignment of its vertices to points in $\mathbb{R}^3$ is flexible. The Jacobi matrix of the map $f$ mapping normalized configurations to edge assignments (see Proposition 1.2) is quadratic and singular. So the three-dimensional analogue of Theorem 1.3 is not true, and the search for another combinatorial analogue is an active research topic in rigidity theory (see 28).

Molecules

For some classes of graphs, the three-dimensional analogue of Theorem 1.3 is true. The most interesting class appears in a statement which used to be called the “Molecular Conjecture”, until it was proved in 30. It is of special interest because it makes a rigidity statement on linkages that appear as models of molecules: atoms are modeled as balls with cylinders attached. A molecular joint is a cylinder that is joined to an atom at both of its ends (see Figure 5). From a kinematic point of view, a molecule model is a linkage with R-joints, such that for each link, all axes of joints attached to this link meet in a fixed point (the center of the atom).

The question of rigidity of molecule models can be reduced to the question of rigidity of particular graphs (see 27). For any graph, we can define its square by drawing an edge between any two vertices of graph distance $2$. A graph is called a square graph if it can be obtained as the square of a subgraph. Now, start with a molecule and draw a graph $G$ with vertices corresponding to atoms and edges corresponding to cylinders in the molecular model. It is clear that every motion of the molecule fixes the length of each edge. However, every such motion also fixes the angle between two cylinders attached to the same atom. But this is equivalent to the statement that the motion fixes the length between the two atoms that are on the other end of the two cylinders. If you add an edge for any two such atoms, then you get exactly the square of $G$.

2. Overconstrained linkages

Let us call a linkage paradoxical if a generic linkage with the same combinatorial structure is rigid, but the linkage itself is mobile. For example, an instance of a Laman graph which is mobile in the plane is paradoxical.

Should we expect paradoxical linkages?

Let us do a simple variable count, as in the CGK estimate, to see if we should be surprised by the existence of paradoxical linkages. Fix a combinatorial structure, for instance a Laman graph $G=(V,E)$. For a generic instance, the number of nonequivalent configurations is finite. These configurations are real solutions of a system of algebraic equations; let $N_G$ be the number of complex solutions of these systems. Note that the number of complex solutions does not depend on the choice of the generic instance, as long as the choice is generic, in contrast to the number of real solutions, which would depend on the choice of a generic instance.

For any system of equations that has finitely many solutions, it is possible to compute a single univariate polynomial, such that the solutions of the system are in bijection with the zeroes of the polynomial. In theory, it is possible to compute such a polynomial as follows. First, introduce a new variable together with a generic linear equation between the new variable and the original variables. Second, eliminate all original variables. You obtain a single polynomial in the new variable. (In practice, it turns out that the elimination is quite costly.) The process can even be carried out in the presence of parameters, which will then also appear in the coefficients of the univariate polynomial. Let us therefore assume that we have now, for each graph $G=(V,E)$, such a polynomial $F_G$, with coefficients depending on an edge length assignment $\lambda$. The degree of $F_G$ would then have to be equal to $N_G$, because it has $N_G$ complex solutions and we may assume that $F_G$ is squarefree.

Now, a labeled graph $(V,E,\lambda )$ is mobile if and only of all $N_G+1$ coefficients of the polynomial are zero, i.e., the polynomial $F_G$ vanishes identically and there are infinitely many configurations. (We have to take nonreal configurations into account, but let us ignore this point for the moment.) The instances of the graph form a family of dimension $|E|$ parametrized by the edge lengths. In order to find a paradoxical linkage, we need to find a solution of a system in $|E|$ variables with $N_G+1$ equations. So we need to compare these two numbers. If the number $|E|$ of variables is bigger than or equal to the number $N_G+1$ of equations, then we should not be surprised by the existence of paradoxical linkages.

Currently, we do not know any lower bounds for $N_G$, but there are conjectured lower bounds which are exponential in $|E|$, so the system of equations that would have to be fulfilled for the parameters of a paradoxical linkage would be highly overdetermined. This is also true for small graphs: for $5\le |V|\le 12$, the numbers $N_G$ are all known 9, and we always have $|E|<N_G+1$. Consequently, the very existence of paradoxical linkages is itself paradoxical! At least, this is so for the type of linkages we considered in this comparison of number of variables and number of equations, namely moving graphs in the plane.

Bipartite graphs

The smallest mobile Laman graphs have six vertices. One is the complete bipartite graph $K_{3,3}$. In 15, Dixon describes a construction to make arbitrary bipartite graphs mobile. The set $V$ of vertices is partitioned into two disjoint subsets $V_1,V_2$. Put all vertices in $V_1$ on the $x$-axis and all vertices of $V_2$ on the $y$-axis. For all edges—say between vertex $i$ on the $x$-axis and vertex $j$ on the $y$-axis—the configuration has to satisfy a length condition $x_i^2+y_j^2=\lambda _{ij}$. If there is no vertex coinciding with the origin, then we can simultaneously decrease all values $x_i^2$ and increase all values $y_j^2$ by the entity $\epsilon$ (sufficiently small). This shows that the linkage is actually mobile.

Using computer algebra, Walter and Husty 47 proved that Dixon’s construction is one of two possible mobile $K_{3,3}$’s; in all other cases, $K_{3,3}$ is rigid. The second mobile $K_{3,3}$, also found in 15, is a mobile $K_{4,4}$ with two points removed; see Figure 6. The configuration has a finite symmetry group, namely the symmetry of a rectangle. Indeed, the points form two rectangles sharing their symmetry axes.

Note that Dixon I applies to arbitrary bipartite graphs. In contrast, the symmetric construction Dixon II does not scale, it just applies to $K_{4,4}$ and its subgraphs.

NAC colorings

Another construction that does scale is based on the possibility of partitioning the set $E$ of edges into two nonempty subsets $E_r,E_b$ of red and blue edges. We assume that every cycle in $G$ is either unicolored or has at least two edges of both colors; especially, triangles are always unicolored. Such a partition is called NAC (no almost (unicolored) cycle) coloring. For each connected component of the subgraph $R_i$ of $(V,E_r)$ we assign a complex number $z_i$, and for each vertex of the subgraph $B_j$ of $(V,E_b)$, we assign a complex number $w_j$. Then we choose a real parameter $t$ parametrizing a periodic motion, as follows: Map any vertex in $R_i\cap B_j$ to the point $z_i+e^{it}w_j\in \mathbb{C}$. Now $\mathbb{C}$ is a model for the plane $\mathbb{R}^2$. Hence we have constructed, for any real value of $t$, a configuration of the graph in $\mathbb{R}^2$. The construction is continuous in $t$, so we may call it a motion. The blue edges always keep their orientation while the red edges are rotated with uniform speed, as in Figure 7.

As a special case of the above construction, we may choose the complex numbers $z_i$ and $w_j$ to be real. Then the configuration corresponding to the “time” value $t=\pi /2$ has the following property: all red edges are parallel to the first coordinate axis and all blue edges are parallel to the second coordinate axis. The whole motion can be constructed by taking a very small moving subgraph, with three vertices and two edges, and completing it by parallel copies of edges. This moving graph is quite boring: at any time, all red edges are parallel and all blue edges are parallel. But wait—we can do the same with other graphs as well! Let us start with a moving quadrilateral. Then we add more edges that are parallel to one of the four edges of the quadrilateral. We get a bigger graph with the property that every motion of the quadrilateral induces a motion of the bigger graph; see Figure 8 for an example.

In Section 6, we will see that the existence of NAC coloring is not only sufficient, but also necessary for the existence of a length assignment that makes a given graph mobile in $\mathbb{R}^2$. This result requires a few tools from algebraic geometry. More examples of graphs moving in the plane and NAC colorings can be found in https://jan.legersky.cz/project/movablegraphs/.

3. Revolute loops and dual quaternions

Let $n\ge 4$. An $n$R chain is a linkage in 3-space consisting of $n+1$ links connected by $n$ revolute joints. In robotics, the first link is called the base and the last link is called the hand or end effector. Each joint can be controlled by an electric motor in such a way that the end effector performs a particular task.

If we firmly connect the first and the last link of an $n$R chain, then we get an $n$R loop: a linkage with $n$ links connected cyclically by $n$ revolute joints. According to the CGK formula, the mobility is $\max (0,n-6)$. If $n\ge 7$, then a generic $n$R loop is generically mobile. A generic 6R linkage is rigid; the number of configurations, including complex solutions, is $16$ (see 44, 11.5.1). For $n=5$ and $n=4$, we obtain an overdetermined system of equations.

Remark 3.1.

Revolute loops may be considered as special cases of linkages of graph type, in the following way: we pick two distinct points on each joint axis and connect them by an edge. For each link, we draw four additional edges connecting the points on the two axes that belong to the link, so that every link carries a complete graph $K_4$, which is geometrically a tetrahedron. We may imagine that the link, as a rigid body, is this tetrahedron, and every edge between the the two points on a rotation axis is a hinge. Let us call such a revolute loop a tetrahedral $n$R loop.

Note that the graph has $2n$ vertices and $5n$ edges. See Figure 9 for an example of a tetrahedral 6R loop.

Even though revolute loops may be considered a subclass of linkages of graph type, it is advantageous to introduce new techniques especially suited for them.

$4\mathrm{R}$ loops

The classification of mobile 4R loops is due to Delassus 12. He proved that there are three types of mobile 4R linkages:

•

Planar. All rotation axes are parallel. Essentially, this is a quadrilateral moving in the plane. The third coordinate is not changed in any of the moving links. A familiar example is shown in Figure 10(a).

•

Spherical. All rotation axes pass through a single point (see Figure 10(b)). Essentially, this is a moving spherical quadrilateral. The planar case may be considered as a limit case of the spherical case.

•

Skew isogram. Bennett 3 discovered a mobile 4R linkage such that the axes of joints attached to the same link are skew, for all four links; see Figure 11. We describe it below in more detail.

Let $L_1$, …, $L_n=L_0$ be the rotation axes in some configuration of an $n$R loop. For $i=0$, …, $n-1$, we assume that the lines $L_i$ and $L_{i+1}$ belong to the $i$th link. Since the link is assumed to be a rigid body, the normal distance and the angle between $L_i$ and $L_{i+1}$ do not change as the linkage moves: they are invariant parameters. Assume that none of the angles is zero, i.e., $L_i$ and $L_{i+1}$ are not parallel. Then there is a unique line $N_i$ intersecting both $L_i$ and $L_{i+1}$ at a right angle. The distance $s_i$ between $N_i\cap L_i$ and $N_{i-1}\cap L_i$ is called the offset. The angles, normal distances, and offsets are $3n$ invariant geometric parameters of the linkage; in robotics, they are called the invariant Denavit/Hartenberg parameters 13. We use the following notation.

•

Angles. $\alpha _i$ is the angle between the lines $L_i$ and $L_{i+1}$.

•

Distances. $d_i$ is the normal distance between the lines $L_i$ and $L_{i+1}$.

•

Offsets. $s_i$ is the distance between two points on $L_i$, namely between the intersection with the common normal of $L_i$ and $L_{i+1}$ and the intersection with the common normal of $L_i$ and $L_{i-1}$.

For a given $n$R loop with fixed invariant parameters, a configuration is determined by the $n$ angles at the rotation axes. The $3n$ invariant Denavit/Hartenberg parameters together with the $n$ configuration parameters determine the positions of the $n$ rotation axes and the position of the links uniquely up to $\mathrm{SE}_3$ (recall that $\mathrm{SE}_3$ is the group of direct isometries from $\mathbb{R}^3$ to itself). These $4n$ parameters fulfill a condition, called the closure equation: we attach an internal coordinate system to each link, with the axis $L_i$ being the $x$ and the common normal $N_i$ being the $z$-axis. Then the transformation of the $i$th coordinate system to the $(i+1)$-th coordinate system is the composition of the translation by a vector of length $d_i$ parallel to the $z$-axis, the rotation around the $z$-axis by the angle $\alpha _i$, the translation by a vector of length $s_i$ parallel to the $x$-axis, and a rotation around the $x$-axis determined by the $i$th configuration parameter. The product of all these $4n$ direct isometries is equal to the identity, and this statement gives the closure equation.

Because the two sides of the closure equation have values in a group, it is more than a single equational constraint. Since the group $\mathrm{SE}_3$ is a smooth manifold of dimension $6$, we can choose six local coordinate functions in a neighborhood $U$ of the identity such that within $U$, the identity is the only point such that all six functions vanish. Then the closure equation is a condition that can be expressed by six equational constraints, namely the six functions evaluated at the left side of the closure equation, plus some open conditions that have no effect on the dimension of the solution set. For any positive integer $k$, let us call a condition which can be locally defined by $k$ a condition of codimension $k$. Then the closure equation is a condition of codimension 6.

A skew isogram is a 4R linkage such that the invariant Denavit/Hartenberg parameters $d_0$, …, $s_3$ satisfy the conditions

$$\begin{equation} \begin{split} &\ \ d_1=d_3,\quad d_0=d_2,\quad \alpha _1=\alpha _3,\quad \alpha _0=\alpha _2,\\ &\frac{d_1}{\sin (\alpha _1)}=\frac{d_0}{\sin (\alpha _0)},\quad s_0=s_1=s_2=s_3=0. \end{split}{\tag{1}} \end{equation}$$

Dual quaternions

In order to prove that the skew isogram is mobile, we use an algebraic way suggested in 46 to parametrize $\mathrm{SE}_3$. The algebra $\mathbb{D}\mathbb{H}$ of dual quaternions was invented by Clifford 10. Modern references for dual quaternions in kinematics are 3742; here we list the relevant definitions and properties.

•

The algebra $\mathbb{H}$ of Hamiltonian quaternions is the four-dimensional vector space over $\mathbb{R}$ generated by $1,\mathbf{i},\mathbf{j},\mathbf{k}$, together with a bilinear and associative multiplication satisfying $\mathbf{i}^2=\mathbf{j}^2=\mathbf{k}^2=\mathbf{i}\mathbf{j}\mathbf{k}=-1$.

•

Conjugation on quaternions is defined as the linear map $\mathbb{H}\to \mathbb{H}$ sending $1$ to itself, $\mathbf{i}$ to $-\mathbf{i}$, $\mathbf{j}$ to $-\mathbf{j}$, and $\mathbf{k}$ to $-\mathbf{k}$. It is an anti-automorphism: for any $p,q\in \mathbb{H}$, we have $\overline{pq}=\overline{q}\,\overline{p}$.

•

The norm of a quaternion $h$ is defined as $N(h)\coloneq h\overline{h}=\overline{h}h$. It is always a nonnegative real number. Moreover, $N$ is a semigroup homomorphism from $(\mathbb{H},\cdot )$ to $(\mathbb{R},\cdot )$.

•

The algebra $\mathbb{D}$ of dual numbers is the associative and commutative algebra over $\mathbb{R}$ generated by $1,\epsilon$, where $\epsilon ^2=0$. For a dual number $a+\epsilon b$, we call $a$ its primal part and $\epsilon b$ its dual part.

•

The algebra $\mathbb{D}\mathbb{H}$ of dual quaternions is obtained by scalar extension (i.e., $\mathbb{D}\mathbb{H}\coloneq \mathbb{H}\otimes _\mathbb{R}\mathbb{D}$). Its vector space dimension over $\mathbb{R}$ is 8, with basis $(1,\mathbf{i},\mathbf{j},\mathbf{k},\epsilon ,\epsilon \mathbf{i},\epsilon \mathbf{j},\epsilon \mathbf{k})$. Multiplication is bilinear over $\mathbb{D}$, and conjugation is $\mathbb{D}$-linear.

•

The norm $N$ extends to a semigroup homomorphism from $(\mathbb{D}\mathbb{H},\cdot )$ to $(\mathbb{D},\cdot )$. Its image is the set of dual numbers with positive primal part together with zero.

We define the $\mathbb{S}\subset \mathbb{D}\mathbb{H}$ as the set of dual quaternions with norm in $\mathbb{R}^\ast$. It is a multiplicative subgroup of $(\mathbb{D}\mathbb{H},\cdot )$. The subset $R^\ast \in \mathbb{S}$ is a normal subgroup of $\mathbb{S}$.

Theorem 3.2.

The quotient group $\mathbb{S}/\mathbb{R}^\ast$ is isomorphic to $\mathrm{SE}_3$.

Sketch of proof.

The isomorphism is determined by a group action of $\mathbb{S}/\mathbb{R}^\ast$ on $\mathbb{R}^3$. We may regard $\mathbb{R}^3$ as the abelian normal subgroup $T$ of $\mathbb{S}/\mathbb{R}^\ast$ of classes represented by dual quaternions of the form $1+x\epsilon \mathbf{i}+y\epsilon \mathbf{j}+z\epsilon \mathbf{k}$ (this subgroup is going to be the subgroup of translations in $\mathrm{SE}_3$). The substitution of $\epsilon$ by $-\epsilon$ is an outer automorphism of $\mathbb{S}/\mathbb{R}^\ast$ of order 2—let us call it $\tau$—which fulfills the following property: if $h\in \mathbb{S}/\mathbb{R}^\ast$, then $h^{-1}\tau (h)\in T$. This implies that for all $h\in \mathbb{S}/\mathbb{R}^\ast$ and $v\in T$, the element $h^{-1}v\tau (h)=(h^{-1}vh)(h^{-1}\tau (h))$ is in $T$, and this defines a right action of $\mathbb{S}/\mathbb{R}^\ast$ on $T$. The bijections of $T$ in the image of this action are direct isometries, and this defines a group isomorphism $\mathbb{S}/\mathbb{R}^\ast \cong \mathrm{SE}_3$.

■

By Theorem 3.2, we have constructed an embedding of $\mathrm{SE}_3$ into the projective space $\mathbb{P}(\mathbb{D}\mathbb{H})\cong \mathbb{P}^7$, as the subset defined by a quadratic form $S=0$, namely the dual part of the norm, and by a quadratic inequation $N\ne 0$, namely the primal part of the norm.

There is a bijection between elements of order 2 in $\mathrm{SE}_3$ and lines in $\mathbb{R}^3$: every line corresponds to a half turn round that line (a rotation by the angle $\pi$). A point in $\mathrm{SE}_3\subset \mathbb{P}(\mathbb{D}\mathbb{H})$ has order 2 if and only if its scalar part is zero. Here we have two linear equations, namely the coefficient of $1$ and the coefficient of $\epsilon$, defining a $\mathbb{P}^5$ in $\mathbb{P}(\mathbb{D}\mathbb{H})$. The intersection of this $\mathbb{P}^5$ with the quadric hypersurface defined by $S$ (a.k.a. the Study quadric) is isomorphic to the Plücker quadric, and the remaining six coefficients are the Plücker coordinates of lines.

Let $l\in \mathbb{D}\mathbb{H}$ be a dual quaternion representing an element of order 2 in $\mathrm{SE}_3$. Then $l^2=-N(l)$ is a negative real number; without loss of generality, we may assume $l^2=-1$. The line connecting $[1]$ and $[l]$ is contained in the Study quadric: its elements are the rotations around the line $L$ corresponding to $l$. (Note that $[1]$ denotes the equivalence class of the dual quaternion $1$ in $\mathbb{P}^7$ and does not indicate a reference to the bibliography.) These elements form a group; indeed, the vector space generated by $1$ and $l$ is a subalgebra isomorphic to $\mathbb{C}$ over $\mathbb{R}$, and the projectivization of this two-dimensional real algebra is a Lie group isomorphic to $\mathrm{SO}_2$. We call this group the revolution with axes $L$ (we prefer not to use the word “rotation” because a rotation is a single group element). A parametric representation of the revolution is $t\mapsto (t+l)$, where the parameter $t$ ranges over the real projective line; the parameter $t=0$ corresponds to $[l]$, and the parameter $t=\infty$ corresponds to $[1]$. In general, the parameter $t$ corresponds to the cotangent of half of the rotation angle.

Remark 3.3.

Conversely, assume that we have a line in $S$ passing through $[1]$. Then we can parametrize it by a linear polynomial in $t$ with leading coefficient $1$, i.e., by a polynomial $(t+h)$ with $h\in S$. Because $N(t+h)=t^2+(h+\bar{h})t+N(h)$ has to be real for all $t\in \mathbb{R}$, it follows that $h+\bar{h}\in \mathbb{R}$: the scalar part of $h$ is real (its dual part is zero). Then a reparametrization of the line is $s\mapsto (s+\frac{h-\bar{h}}{2})$, setting $s=t+\frac{h+\bar{h}}{2}$. This reparametrization shows that the line parametrizes a revolution with axis corresponding to $[h-\bar{h}]$, except in the case when $N(h-\bar{h})=0$. In the exceptional case, the line will parametrize a translation along a fixed direction.

Let us now study conics passing through $[1]$ and contained in the Study quadric. Any such conic has a quadratic parametrization $t\mapsto (t^2+at+b)$ where $a,b\in \mathbb{D}\mathbb{H}$. Does this quadric polynomial factor into two linear polynomials? And if yes, do the linear polynomials parametrize revolutions? To answer these questions, we study $\mathbb{D}\mathbb{H}[t]$, the noncommutative algebra of univariate polynomials with coefficients in $\mathbb{D}\mathbb{H}$, where the variable $t$ is supposed to be central, i.e., it commutes with the coefficients.

Quaternion polynomials

As a preparation, let us ask the analogous question for the noncommutative algebra $\mathbb{H}[t]$. We will show that here, every polynomial can be written as a product of linear factors; in other words, the skew field of quaternions is algebraically closed! The proof is taken from 22.

Lemma 3.4 (Polynomial division).

Let $A,B\in \mathbb{H}[t]$, $B\ne 0$. Then there exist unique polynomials $Q,R\in \mathbb{H}[t]$ such that $A=QB+R$ and either $\deg (R)<\deg (B)$ or $R=0$.

Proof.

See 25, Lemma 1.

■

If $\deg (B)=1$ in Lemma 3.4, say $B=t-h$, then $R$ is a constant in $\mathbb{H}$. The constant is zero if and only if $(t-h)$ is a right factor of $A$. If this is true, then we also say “$h$ is a right zero of $A$”. So, the questions is, Does every polynomial $A$ of positive degree have a right zero? And maybe we are also interested in the question of how to find it.

A right zero of $A$ is also a right zero of the norm polynomial $N(A)=\bar{A}A$. We know that the norm polynomial is in $\mathbb{R}[t]$. It is also the sum of four squares—if $A=A_0+A_1\mathbf{i}+A_2\mathbf{j}+A_3\mathbf{k}$, then $N(A)=A_0^2+A_1^2+A_2^2+A_4^2$. If $N(A)$ has a real zero $r$, then this real zero is also a zero of $A_0,A_2,A_2,A_3$; hence it is a zero of $A$, and we have found what we wanted to find.

What do we do if $N(A)$ has no real zeroes? In this case, we choose a quadratic irreducible factor $M\in \mathbb{R}[t]$. By Lemma 3.4, there are $Q,R\in \mathbb{H}[t]$, with $\deg (R)<2$ or $R=0$, such that $A=QM+R$. We distinguish three cases.

(1)

If $R=0$, then $M$ is a right factor of $A$. Every right zero of $M$ is also a right zero of $A$. So it suffices to show that $M$ has a right zero. But we know that $M$ has a complex zero. So, assume that $z=a+\mathrm{i} b$ is a complex zero of $M$, for some $a,b\in \mathbb{R}$, $b\ne 0$. Then we have the equation $M=(t-a-\mathrm{i} b)(t-a+\mathrm{i} b)$ between complex polynomials. But now we can replace the complex number $\mathrm{i}$ by the dual quaternion $\mathbf{i}$, which also fulfills the equation $\mathbf{i}^2+1=0$. It follows that $M=(t-a-\mathbf{i} b)(t-a+\mathbf{i} b)=0$, and $a-\mathbf{i} b$ is a right zero of $M$ and also a right zero of $A$.

(2)

If $\deg (R)=1$, say $R=ut+v$ for suitable $u,v\in \mathbb{H}$, $u\ne 0$, then $h\coloneq -u^{-1}v$ is a right zero of $R$. Since$$\begin{equation} \overline{R}{R}=(\overline{A}-\overline{Q}M)(A-QM)=N(A)+M(-\overline{Q}A-\overline{A}Q+\overline{Q}QM) {\tag{2}} \end{equation}$$

is a multiple of $M$, and $\deg (\overline{R}{R})=\deg (M)=2$, it follows that $M$ is a left multiple of $R$. It follows that $h$ is right zero of $M$. Hence it is also a right zero of $A=QM+R$.

(3)

If $\deg (R)=0$, then equation 2 is self-contradictory: the right side is a multiple of $M$, and the left side is a nonzero constant. So, this case cannot occur.

Theorem 3.5.

Every polynomial in $\mathbb{H}[t]$ can be written as a product of linear polynomials.

The proof is clear by now: given $A$ of positive degree, we can find a right $h$, write $A=A'(t-h)$, and iterate.

How many distinct factorizations do there exist? Starting with one factorization, we may get infinitely many distinct factorizations by multiplying with constants and their inverses in between the linear factors. In order to get rid of these “essentially same” factorizations, it suffices to assume that the polynomial $A$ and the linear factors are monic, i.e., they have leading coefficient 1.

If $A$ is a multiple of an irreducible real quadric $M$ (the first case in the above case distinction), then $A$ has infinitely many right zeroes (see 22). But if not, then the number of distinct factorizations is finite. Indeed, the only nondeterministic step in the iterative procedure sketched above is the choice of the sequence of irreducible factors used for factoring out the right zeroes. In particular, we have the following.

Proposition 3.6.

A monic polynomial of degree $d$ with generic coefficients has exactly $d!$ distinct factorizations into monic linear factors.

The comparison with polynomial factorization in $\mathbb{C}[t]$ is illuminating: there, the factorization is unique. But if we consider two factorizations which differ only by the order of the factors as being distinct, then we have again $d!$ distinct factorizations. In the case of $\mathbb{H}[t]$, permutation of factors would not lead to the same product, because $\mathbb{H}[t]$ is not commutative; hence permutation is not a method to get more factorizations, and all $d!$ factorizations are different.

Mobility of the skew isogram

Feeling well prepared? Then, let us go back to polynomials over the dual quaternions. The connection between linkages and factorizations of dual quaternion polynomials is the following observation.

Proposition 3.7.

Let $P\in \mathbb{D}\mathbb{H}[t]$ be a polynomial of degree $n$ that parametrizes a curve in the Study quadric. Assume that $P$ can be written as a product of linear factors parametrizing revolutions. Then there exists an open $(n+1)$R chain and a motion of this chain such that $P$ parametrizes the motion of the end effector.

Proof.

We write $P=P_1\cdots P_n$; for $r=1$, …, $n$, the linear factor $P_r$ parametrizes a revolution, say with axis $L_i$. We connect the basis to the first link by an R-joint with axis $L_1$, the first link to the second link by an R-joint with axis $L_2$, and so on. We move the chain so that the relative motion of the $(i+1)$-st link with respect to the $i$th link is parametrized by $P_i$. Then the link of the end effector is parametrized by $P_1P_2\cdots P_n=P$.

■

Here is a concrete example: the polynomial $P_1=t-\mathbf{i}$ parametrizes a revolution around the $x$-axis. The polynomial $P_2=t+\mathbf{i}+\epsilon \mathbf{j}$ parametrizes a revolution with a parallel rotation axis. We may think of $P_1$ as the motion of a rotating wheel, and $P_2$ as the relative motion of a rod joined to the wheel, which is moved so that it always stays parallel to the $y$-axis. The rod is our end effector: its motion is parametrized by $P_1P_2=t^2+1-\epsilon \mathbf{k}$. It consists of translations, by a vector following a circle in the $yz$-plane.

Let us assume that we have given a polynomial $P\in \mathbb{D}\mathbb{H}[t]$ that parametrizes a curve in the Study quadric. We can try to copy the factorization strategy that worked in $\mathbb{H}[t]$: factorize the norm polynomial $N(P)$, choose a quadratic irreducible factor $M$ (let us assume that $N(P)$ has no real zeroes for now), compute the remainder of $P$ modulo $M$; if this remainder is a linear polynomial $R=ut+v$ for some $u,v\in \mathbb{D}\mathbb{H}$, compute a right zero $h\coloneq u^{-1}v$, factor out $(t-h)$ from the right, and iterate. This is going to work for generic coefficients. Moreover, since $N(P(t_0))$ is in $\mathbb{R}$ (and not in $\mathbb{D}\setminus \mathbb{R}$) for all $t_0\in \mathbb{R}$, the norm polynomial $N(P)$ is in $\mathbb{R}[t]$. Therefore it has a factorization into irreducible factors in $M_r\in \mathbb{R}[t]$, $r=1$, …, $\deg (P)$. The right factors $(t-h_r)$ produced by our strategy satisfy the equation $(t-h_r)(t+h_r)=M_r$, so by Remark 3.3, the linear factor will generically parametrize a revolution. So, at least generically, everything is fine!

The application of our strategy leads to the following characterization of skew isograms. It was first found in 8 by different methods.

Theorem 3.8.

For a generic conic in the Study quadric passing through $[1]$, there is a skew isogram such that the conic parametrizes the motion of the second link. (In particular, this skew isogram is mobile.)

Proof.

Let $P=t^2+at+b$ be a quadratic parametrization of the conic, with $a,b\in \mathbb{D}\mathbb{H}$. The norm $N(P)$ is a real polynomial that has only nonnegative values. By genericity, it has no double zeroes, and it can be written as a product $M_1M_2$ of two distinct quadratic irreducible factors. For $i=1,2$, we construct as above a factorization $P=(t-r_i)(t-w_i)$ such that $N(t-w_i)=M_i$. (It follows that $N(t-r_i)=N(t-w_{2-i})$, for $i=1,2$.)

The linear polynomials $t-r_1,t-w_1,t-r_2,t-w_2$ parametrize lines on the Study quadric. Each of them corresponds to a subgroup of rotations around a line in $\mathbb{R}^3$. Let $L_1,K_1,L_2,K_2$ be these four lines, respectively. We construct a mobile 4R loop as follows: the base link contains the lines $L_1$ and $L_2$; the first link contains the lines $L_1$ and $K_1$; the second link contains the lines $K_1$ and $K_2$; and the third link contains the lines $L_2$ and $K_2$. For each $t\in (\mathbb{R}\cup \{\infty \})$, we get a configuration of the 4R loop: the relative displacement of the first link with respect to the base link is the rotation $t-r_1$; the relative displacement of the third link with respect to the base link is the rotation $t-r_2$; the relative motion of the second link with respect to the first link is the rotation $t-w_1$; and the relative motion of the second link with respect to the third link is the rotation $t-w_2$. The relative position of the second link with respect to the base link can be computed in two ways, via the first link or via the third link. In both ways, the result is $(t-r_1)(t-w_1)=(t-r_2)(t-w_2)=P$.

Once the lines are constructed, it is straightforward to compute the invariant Denavit/Hartenberg parameters of the 4R loop; we omit this calculation. The result is exactly what is shown in equations 1. It follows that the 4R loop is a skew isogram.

■

The paper 8 also contains the converse statement: for any skew isogram, the relative motion of two links that are not connected by a joint is parametrized by a conic curve on the Study quadric that passes through $[1]$. In 25, factorizations of cubic polynomials in $\mathbb{D}\mathbb{H}[t]$ are used to construct paradoxically mobile 5R loops and 6R loops.

Drawing rational curves

It is time to lift the veil of mystery about the ellipse circle shown in Figure 1. This example is taken from 19, which contains a construction of a linkage that draws a rational plane curve. In 34, the construction is extended to rational space curves. An online illustration with several examples can be found at http://www.koutschan.de/data/link/.

The ellipse with implicit equations $\frac{(x+a)^2}{a^2}+\frac{y^2}{b^2}=z=0$ has a rational parametrization

$$\begin{equation*} (x,y,z) = p(t) \coloneq \left( \frac{-2a}{t^2+1},\frac{2bt}{t^2+1},0 \right) . \end{equation*}$$

For any $t\in \mathbb{R}$, the dual quaternion $1+\epsilon (\frac{-a}{t^2+1}\mathbf{i}+\frac{bt}{t^2+1}\mathbf{j})$ represents a translation that maps the origin to $p(t)$. The equivalence class of a dual quaternion is not changed when we multiply it with $t^2+1$. So we set $P\coloneq t^2+1+\epsilon (-a\mathbf{i}+bt\mathbf{j})$ and try to factorize. The norm polynomial is $(t^2+1)^2$, hence our only choice of an irreducible factor is $M=t^2+1$. The remainder of $P$ modulo $M$ is $R=\epsilon (-a\mathbf{i}+bt\mathbf{j})$. But now something is wrong: even though $R$ has a right zero, namely $h=-\frac{b}{a}\mathbf{k}$, there is no common zero of $R$ and $M$ except in the case $a=\pm b$. (If $a=\pm b$, then the ellipse is a circle, and we are not interested.) The argument we used in the quaternion case fails because $N(R)=0$.

There is a way out: instead of factorizing $P$, we can factorize $Q\coloneq (t-\mathbf{i})P$. The displacement $[t-\mathbf{i}]$ fixes the origin, hence the displacement $[Q(t)]$ maps the origin to the point $p(t)$, just like the translation $[P(t)]$. After all, there are many motions such that the origin traces the ellipse, and we just choose a different one.

The remainder of $Q$ modulo $M$ is $\epsilon (b-a)(\mathbf{i} t-\mathbf{j})$, and this time we do have a common right zero of $M$ and $R$! Any dual quaternion of the form $-k-\epsilon (c\mathbf{j}+d\mathbf{j})$ is fine. For simplicity, we set $d=0$. Now we can factor $(t+k+\epsilon c\mathbf{j})$ from the right and proceed. The final result is

$$\begin{equation*} \begin{split} Q &= (t-\mathbf{k}+(a/2+b/2)\epsilon \mathbf{j})(t-\mathbf{k}+(-a/2+b/2-c)\epsilon \mathbf{j})(t+\mathbf{k}+\epsilon c\mathbf{j})\\ &=(t-h_1)(t-h_2)(t-h_3). \end{split} \end{equation*}$$

(We leave the remaining steps as an exercise—they are not problematic and give a unique result.)

In order to construct a linkage with mobility $1$, we could use another factorization with a different linear factor on the left. But such a factorization does not exist: the norm polynomial of $Q$ is $(t^2+1)^3$, so there is no choice of choosing different factors of the norm polynomial. We need to mix a different quadratic irreducible polynomial into our soup.

Let $d\in \mathbb{R}$ and define $h_0\coloneq 2\mathbf{k}+d\epsilon \mathbf{j}$. The polynomial $(t-h_0)(t-h_1)$ has exactly two factorizations—one we know already, the second one is $(t-h_4)(t-h_5)$, for some $h_4,h_5\in \mathbb{D}\mathbb{H}$. Then the polynomial $(t-h_5)(t-h_2)$ also has exactly two factorizations, and we can define two more dual quaternions such that the second factorization is $(t-h_6)(t-h_7)$. Finally, let $h_8,h_9\in \mathbb{D}\mathbb{H}$ such that $(t-h_7)(t-h_3)=(t-h_8)(t-h_9)$. The different factorizations giving the same result correspond to paths in the directed graph $G$ in Figure 12 with equal starting and ending vertex.

The linkage drawing an ellipse now consists now of eight links corresponding to the eight vertices of $G$. Two links are connected by a joint if and only if the vertices are connected by an edge. The label of the edge—a linear polynomial in $\mathbb{D}\mathbb{H}$—parametrizes the relative position of the target link with respect to the source link. As $t$ varies, the linear polynomials parametrize a revolution. Therefore, the two links are connected by an R-joint. Now we fix the link corresponding to vertex 4. Then the relative motion of the link corresponding to vertex 1 maps the origin to the point $p(t)$ on the ellipse.

Note that $b=0$ is allowed; in this case, the ellipse degenerates to a line segment traced twice, and we have constructed a linkage that draws this line.

4. Symmetry

The second construction by Dixon of a moving $K_{4,4}$ is symmetric. Indeed, symmetry may change the counting rules and can sometimes be the explanation of paradoxical mobility. We discuss here two cases in more detail: line symmetry and plane symmetry. Both cases appeared in Bricard’s families of moving octahedra in 5. Schulze 43 was the first to describe paradoxical moving symmetric graphs systematically, in every dimension.

Line symmetry

We assume that we have a graph $G=(V,E)$ such that $|E|=3|V|-6$, and an assignment $(\lambda )_{e\in E}$ of a positive real number for each edge. Generically, the configuration set, i.e., the set of all maps $V\to \mathbb{R}^3$ respecting edge lengths modulo $\mathrm{SE}_3$, is finite: we have $3|V|-6$ variables and $|E|$ equations. Let us now assume that we have a graph automorphism $\tau :V\to V$ that preserves the edge assignment. Assume also that $\tau$ has order 2, does not fix a vertex, and does not fix an edge—a priori, an edge could be fixed if $\tau$ permutes its two vertices. Then $|V|$ consists of $n\coloneq \frac{|V|}{2}$ pairs of conjugated vertices, and $E$ consists of $3n-3$ pairs of conjugated edges. In order to construct line symmetric configurations, we fix a line $L\subset \mathbb{R}^3$; let $\sigma :\mathbb{R}^3\to \mathbb{R}^3$ be the rotation around $L$ by $\pi$. For any conjugated pair $(v,\tau (v))$ of vertices, we pick one point $p_v$ anywhere in $\mathbb{R}^3$; the second point is determined by $p_{\tau (v)}\coloneq \sigma (p_v)$. The number of variables to specify all points is $3v$. There is also a two-dimensional subgroup of $\mathrm{SE}_3$ fixing $L$, generated by rotations around $L$ and translations into the direction of $L$. We use two of the variables to get a canonical representative. Hence the number of variables to specify an equivalence class of configurations is $3n-2$. The number of equations is equal to the number of pairs of conjugated edges, which is $3n-3$, because conjugated edges always have the same length. Hence the expected mobility is $1$.

The smallest line symmetric moving graph is the 1-skeleton of an octahedron, with six vertices and 12 edges. The group of graph automorphisms is isomorphic to the Euclidean symmetry group of a regular octahedron, which has 48 elements. There is a unique automorphism of order 2 without fixed vertex and fixed edge, corresponding to the point reflection of the regular octahedron. The construction applies, and we get a moving line symmetric octahedron (see Figure 13, left side). Bricard 7 proved that there are three types of moving octahedra, and the line symmetric mechanism is one of the three.

Proposition 4.1.

Let $\Gamma$ be a centrally symmetric convex polyhedron with only triangular faces. Then its $1$-skeleton $G=(V,E)$ allows a line symmetric motion.

Proof.

By Euler’s formula, the number of edges is $3|V|-6$. The point reflection acting on $\Gamma$ defines an automorphism of the graph which satisfies the required properties: order 2, no fixed vertex, no fixed edge. Our construction applies: for any conjugated pair of vertices, we choose one point generically and the second by line reflection. By the above counting of indeterminates and constraints, the expected mobility is $1$.

■

For instance, we may construct a line symmetric moving icosahedron with 12 vertices and 30 edges.

Remark 4.2.

Be careful: the point symmetry defines only the graph automorphism! It is geometrically different from the line symmetry in all configurations we allow. Point symmetric configurations do also exist, but only finitely many.

Another classical example is Bricard’s line symmetric 6R loop. Any 6R loop consists of six links, cyclically connected by revolute joints that allow rotations around an axes which is common to the two attached links; generically, a 6R loop is rigid.

Recall that configurations can be found by solving the closure equation (see Section 3): we attach an internal coordinate system to each link and parametrize the transformation $T_i$ from the $i$th link to the $(i+1)$-th link (where the sixth link is the zeroth link) by the $i$th configuration parameter $\phi _i$. As mentioned above, $T_i(\phi _i)$ is the composition of the translation by a vector of length $d_i$ parallel to the $z$-axis, the rotation around the $z$-axis by the angle $\alpha _i$, the translation by a vector of length $s_i$ parallel to the $x$-axis, and a rotation around the $x$-axis determined by the $i$th configuration parameter $\phi _i$. The configuration set is the set of solutions $(\phi _0,\dots ,\phi _5)$ of the closure equation

$$\begin{equation*} T_0(\phi _0)T_1(\phi _1)T_2(\phi _2)T_3(\phi _3)T_4(\phi _4)T_5(\phi _5) = e , \end{equation*}$$

where $e$ is the identity of the group $\mathrm{SE}_3$. The functions $T_0$, …, $T_5$ depend on the invariant Denavit/Hartenberg parameters, and as a consequence we have $T_0=T_3$, $T_1=T_4$, and $T_2=T_5$. Recall that the closure equation is a codimension 6 condition, because $\mathrm{SE}_3$ is a six-dimensional group, hence the CGK formula estimates that there are only finitely many solutions.

Proposition 4.3.

If the $18$ invariant Denavit/Hartenberg parameters $d_0$, …, $s_5$ satisfy the conditions

$$\begin{equation*} d_i=d_{i+3},\quad \alpha _i=\alpha _{i+3},\quad s_i=s_{i+3}\qquad \text{for } i=0,1,2 , \end{equation*}$$

then there is generically a one-dimensional set of line symmetric configurations.

Proof.

The condition of the invariant Denavit/Hartenberg parameters implies the equations $\phi _0=\phi _3$, $\phi _1=\phi _4$, and $\phi _2=\phi _5$. The closure equation reduces to

$$\begin{equation*} \left(T_0(\phi _0)T_1(\phi _1)T_2(\phi _2)\right)^2 = e . \end{equation*}$$

We ignore the solutions of $T_0(\phi _0)T_1(\phi _1)T_2(\phi _2)=e$ (these are at most finitely many). This means, we search for configuration parameters such that the transformation of the coordinate system of the zeroth link to the coordinate system of the third link is a half turn $x$. This is a codimension 2 condition: as we mentioned in Section 3, the set of involutions in $\mathrm{SE}_3$ is a four-dimensional manifold. The half turn $x$ is the claimed line symmetry: it maps the $i$th link to the $(i+3)$-rd link, for $i=0,1,2$.

■

Remark 4.4.

Is there a good reason to explain the mobility of a line symmetric linkage by the closure equation, instead of just considering them as special cases of line symmetric linkages of graph type, as in Remark 3.1. Here is one: we may replace some of the revolute joints by other types of joints, like prismatic joints, as in hydraulic rams, or helical joints, as commonly seen in the form of nuts and bolts. In both cases, such a joint allows a one-parameter subgroup of displacements of the connected links, and exactly the same proof of mobility is valid. On the other hand, a loop with helical joints cannot be considered as a linkage of graph type, because its closure equation is not even algebraic.

Yet another classical example, the line symmetric Gough–Stewart platform, will be explained in Section 5. Also Bennett’s skew isogram, discussed in Section 3, is a line symmetric mechanism.

Plane symmetry

Plane reflections are involutions in the group $\mathrm{E}_3$ of isometries reversing the orientation. They are of course not direct isometries, but they still may be responsible for paradoxical mobility of various types of linkages, similar to half turns in the case of line symmetric linkages. Let us start with 6R loops. In a plane symmetric configuration of a 6R loop, there exists a plane reflection mapping link 0 to link 5, link 1 to link 4, and link 2 to link 3. The existence of a plane symmetric configuration has the following implication on the invariant Denavit/Hartenberg parameters:

$$\begin{equation} \begin{split} d_0=d_5,\quad d_1&=d_4,\quad d_2=d_3,\\ \alpha _0=\alpha _5,\quad \alpha _1&=\alpha _4,\quad \alpha _2=\alpha _3,\\ s_1=-s_0,\quad s_2=&-s_5,\quad s_0=s_3=0. \end{split}{\tag{3}} \end{equation}$$

Conversely, the above condition imply plane symmetric mobility, as follow.

Proposition 4.5.

Assume that the $18$ invariant Denavit/Hartenberg parameters of a $6\mathrm{R}$ loop satisfy condition 3. Then the $6\mathrm{R}$ loop generically has a one-dimensional set of plane symmetric configurations.

Proof.

The relations between the functions in the closure equations are the following:

$$\begin{gather*} RT_0(\phi _0)R=T_0(-\phi _0),\qquad RT_1(\phi _1)R=T_5(-\phi _1),\\ RT_2(\phi _2)R=T_4(-\phi _2),\qquad RT_3(\phi _3)R=T_3(-\phi _3), \end{gather*}$$

where $R$ is the reflection by the coordinate plane $\Pi$ spanned by the first and second axes. Instead of solving the closure equation, we find all quadruples $(\phi _0,\phi _1,\phi _2,\phi _3)$ such that $RXR=X$, where $X\coloneq T_0(\phi _0)T_1(\phi _1)T_2(\phi _2)T_3(\phi _3)$. An element $X\in \mathrm{SE}_3$ fulfills the equation $RXR=X$ if and only if it is a rotation with an axis orthogonal to $\Pi$ or a translation by a vector in $\Pi$. These rotations and translations form a manifold of dimension 3 (isomorphic to $\mathrm{SE}_2$), hence the condition above is a codimension $6-3=3$ condition. In general, there is a one-dimensional set of solutions.

For every solution $(\phi _0,\phi _1,\phi _2,\phi _3)$ of $RXR=X$, the six-tuple

$$\begin{equation*} (2\phi _0,\phi _1,\phi _2,2\phi _3,\phi _2,\phi _1) \end{equation*}$$

is a solution of the closure equation,

$$\begin{equation*} \begin{split} T_0&(2\phi _0)T_1(\phi _1)T_2(\phi _2)T_3(2\phi _3)T_4(-\phi _2)T_5(-\phi _1)\\ &=T_0(\phi _0)XT_3(\phi _3)RT_2(-\phi _2)T_1(-\phi _1)R\\ &= RT_0(-\phi _0)RXRT_3(-\phi _3)T_2(-\phi _2)T_1(-\phi _1)R\\ &= RT_0(-\phi _0)RXRX^{-1}T_0(\phi _0)R = e. \end{split} \end{equation*}$$

Hence we again get a mobile 6R loop, also known as Bricard’s plane symmetric $6\mathrm{R}$ linkage.

■

Remark 4.6.

As in Remark 4.4, we may replace some of the revolute joints by prismatic or helical joints; see 2. Care has to be taken for the special role of the zeroth joint and the third joint, because these two joints are supposed to be mapped to their own inverse by the plane symmetry. This is not possible at all for helical joints. Prismatic joints are fine, but the direction vector has to be perpendicular to the symmetry plane and not parallel to it.

For linkages of graph type, there is also a construction of plane symmetric linkages that are paradoxically mobile. We assume that we have a graph $(V,E)$ such that is generically rigid and satisfies $|E|=3|V|-6$, for instance the 1-skeleton of a convex polyhedron with triangular faces. Assume that we have a graph automorphism $\tau :V\to V$ of order 2 that fixes $2m$ vertices and $2m-2$ edges, for some $m\ge 1$. Choose a generic edge assignment that respects the involutive symmetry. Fix a plane $\Pi$ in $\mathbb{R}^3$, and let $R:\mathbb{R}^3\to \mathbb{R}^3$ be the reflection at $\Pi$. A configuration $(p_v)_{v\in V}$ is symmetric with respect to the plane $\Pi$ if and only if $R(p_v)=p_{\tau (v)}$ holds for all $v\in V$. The number of indeterminates is $3\frac{|V|-2m}{2}+4m-3=\frac{3}{2}|V|+m-3$: for each 2-orbit in $V$, the realization is determined by three indeterminates, and for each fixed point, we have two indeterminates because the point must lie in $\Pi$. The symmetry group of the plane has dimension 3, which reduces the number of indeterminates of equivalence classes by 3. The number of equations is $\frac{|E|-2m+2}{2}+2m-2=\frac{3|V|-2m-4}{2}+2m-2=\frac{3}{2}|V|+m-4$. Again, we obtain a paradoxically mobile graph.

So, how do we find graphs with an automorphism of order 2 fixing $2m$ vertices and $2m-2$ edges? Say, the graph is the 1-skeleton of a convex polyhedron $\Gamma$ with triangular faces. If $\Gamma$ is symmetric with respect to the half turn around a line passing through two vertices, then we get a involution with two fixed points and no fixed edge, so that $m=1$. This works, for example, for the octahedron (see Figure 13 right side) and for the icosahedron.

Remark 4.7.

In the construction above, there are two geometric symmetries playing entirely different roles: the line symmetry of the convex polyhedron defines a graph automorphism of order 2 with the right properties; the plane symmetry defines a condition on the configurations that we consider. See also Remark 4.2.

Here is an example of a generically rigid graph with 12 vertices and 30 edges and with an automorphism of order 2 that fixes four vertices and two edges: take a 6R loop and construct a graph as in Remark 3.1, by putting two vertices on each of the four rotation axes. In this case, the plane symmetric construction just gives plane symmetric 6R loops, which we have constructed in another way.

Remark 4.8.

A different notion of line/plane/point symmetry for motions is used, for instance, in 48 (for line reflections): here one considers the set of displacements that are reflections at a moving line, plane, or point, followed by a fixed reflection. Because the composition of two point reflections is a translation, a point symmetric motion would be purely translational.

5. Multipods and group-leg duality

The Prix Vaillant 1904 asked for curves in the Lie group $\mathrm{SE}_3$ of direct isometries such that “many” points in $\mathbb{R}^3$ move on spheres. Connecting the moving points by bars with the centers of these spheres, we obtain a multipod, also known as Gough–Stewart platform, which is a linkage consisting of a fixed base and a moving platform that are connected by legs of fixed length that are attached to platform and base by spherical joints (see Figure 14). Flight simulators or other linkages that are supposed to make irregular motions are often manufactured as hexapods with additional prismatic joints at each leg that change its length; in this section, as already stated, the leg lengths remain constant. Each leg gives a codimension 1 condition on the displacement of the platform with respect to the base, hence the CGK formula gives the estimate $\max (0,6-n)$ for the mobility an $n$-pod. Strictly speaking, each leg may be considered as a link that may also revolve around the line connecting its two anchor points, but we disregard this component of the motion. So, pentapods are generically mobile, and hexapods are generically rigid.

A displacement $\mathbb{R}^3\to \mathbb{R}^3$ of the platform relative to the base is given by a special orthogonal matrix $M\in \mathrm{SO}_3$ and the image $y\in \mathbb{R}^3$ of the origin of the base. We set $x\coloneq -M^ty=-M^{-1}y$ to be the preimage of the origin of the platform and $r\coloneq \langle x,x\rangle = \langle y,y\rangle$, where $\langle \cdot , \cdot \rangle$ is the Euclidean scalar product. If we take coordinates $m_{11}$, …, $m_{33}$, $x_1$, $x_2$, $x_3$, $y_1$, $y_2$, $y_3$, and $r$, together with a homogenizing variable $h$, in $\mathbb{P}^{16}$, then a direct isometry defines a point in projective space satisfying $h \neq 0$ and

$$\begin{equation} \begin{gathered} M M^t \; = \; M^t M \; = \; h^2 \cdot \mathrm{id}_{\mathbb{R}^3}, \quad \mathrm{adj}(M) \; =hM^t , \\ M^t y + h x \; = \; 0, \quad M x + h y \; = \; 0 , \\ \langle x,x \rangle \; = \; \langle y,y \rangle \; = \; r h, \end{gathered} {\tag{4}} \end{equation}$$

where $\mathrm{adj}(M)$ is the adjugate matrix. Recall that $A\cdot \mathrm{adj}(A)=\mathrm{adj}(A)\cdot A=\det (A)\cdot \mathrm{id}_{\mathbb{R}^3}$ for any $A\in \mathbb{R}^{3\times 3}$, therefore the above equations imply $\det (M)=h^3$. The equations 4 define a variety $X$ of dimension 6 and degree 40 in $\mathbb{P}^{16}$, whose real points satisfying $h \neq 0$ are in one-to-one correspondence with the elements of $\mathrm{SE}_3$. We call it the group variety; its projective space $\mathbb{P}^{16}$ containing $X$ is called group space.

Mathematically, a leg is a triple $(a,b,d)$, where $a\in \mathbb{R}^3$ is a point of the base, $b\in \mathbb{R}^3$ is a point of the platform, and $d\in \mathbb{R}$ is a positive number, the length of the leg. We define the leg variety $Y$ as the cone over the Segre variety $\Sigma _{3,3} \cong \mathbb{P}^3\times \mathbb{P}^3$ in the projective space $\check{\mathbb{P}}^{16}$; recall that the Segre variety is a subvariety of a projective space of dimension 15 and degree ${3+3\choose 3}=20$, hence $Y$ has dimension $7$ and degree $20$. The values of projective coordinates of a leg $(a,b,d)$ are $u\coloneq 1$, $a_i$, $b_j$ and $z_{ij}\coloneq a_ib_j$ for $i,j=1,2,3$, and the corrected leg length $l \coloneq \langle a, a \rangle + \langle b, b \rangle - d^2$. Note that the indices $i$ and $j$ in $a_i$ and $b_j$ refer to coordinates in $\mathbb{R}^3$ and not to leg numbers. In total, we have 17 variables including the homogenization variable $u$. So, we have the homogeneous variables of a projective space of dimension 16 containing $Y$. We call it leg space and denote it by $\check{\mathbb{P}}^{16}$.

The reason for this very specific choice of coordinates is the following. The algebraic condition $\langle Ma+y-b,Ma+y-b\rangle = d^2$ is bilinear in these coordinates:

$$\begin{equation} \begin{gathered} l h + u r - 2 \sum _{i=1}^3 a_ix_i - 2 \sum _{j=1}^3 b_jy_j - 2 \sum _{i, j = 1}^{3} z_{ij} m_{ij} \; = \; 0. \end{gathered} {\tag{5}} \end{equation}$$

Hence it defines a duality between group space and leg space. Every point in group space, in particular every group element, corresponds to a hyperplane in leg space; every point in leg space, in particular every leg, corresponds to a hyperplane in group space. More generally, to every $k$-plane in group space there is a dual $(15-k)$-plane in leg space, for $k=0$, …, $15$.

The duality has various implications for multipods, whether they are paradoxical or not. To start with, choose six generic legs. They span a generic 5-plane in leg space. The dual 10-plane in group space is also generic and, since it has codimension 6, intersects $X$ in $\deg (X)=40$ points (real or complex). Hence a generic hexapod has 40 configurations, possibly complex. This result has been proved by various methods; see 1735364041.

Now, we choose five generic legs. They span a generic 4-plane in leg space, dual to a generic 11-plane in group space, which intersects $X$ in a curve $C$ of degree 40: the configuration curve of a generic pentapod. We can compute its genus. We first compute the Hilbert series of $X$ from a generating set of its ideal: $H(X)(t)=\frac{1+10t+18t^2+10t^3+t^4}{(1-t)^7}$. Because $C$ is a codimension 5 subvariety of $X$ defined by five linear forms, we may compute the Hilbert series of $C$ from the Hilbert series of $X$:

$$\begin{equation*} \begin{split} H_C(t) &= H_X(t)(1-t)^5 = \frac{1+10t+18t^2+10t^3+t^4}{(1-t)^2}\\ &=1+12t+41t^2+80t^3+120t^4+\cdots . \end{split} \end{equation*}$$

This implies that $C$ is a curve of genus 41 and its embedding in $\mathbb{P}^{11}$ is half canonical.

The Bricard/Borel infinity-pod

Here is the infinity-pod that was given by the two winners of the Prix Vallaint, Borel 4 and Bricard 6. We intersect $X$ with the 3-space defined by

$$\begin{equation*} \begin{split} r+\beta h-2\alpha m_{11} &= m_{11}-m_{22} = m_{12}+m_{21} = m_{33}-h = x_{3}+y_{3}\\ &= m_{13} = m_{23} = m_{31} = m_{32} = x_1 = x_2 = y_1 = y_3 = 0, \end{split} \end{equation*}$$

where $\alpha ,\beta \in \mathbb{R}$ are real parameters such that $\alpha \ne 0$. The result is a quartic curve defined by the equations

$$\begin{equation*} m_{11}^2+m_{12}^2-h^2=x_3^2-2\alpha m_{11}h+\beta h^2 = 0 \end{equation*}$$

and by the linear equations above. It parametrizes a motion $C$ contained in the two-dimensional stabilizer of the third axes $L$, generated by rotations around $L$ and translations in the direction of $L$. The dual 12-plane in leg space is defined by

$$\begin{equation*} z_{12}-z_{21} = z_{11}+z_{22}-\alpha u = a_3-b_3 = l-2z_{33}-\beta u = 0 . \end{equation*}$$

A leg $(a,b,d)$ in the intersection with $Y$ if and only if

$$\begin{equation*} a_1b_2-a_2b_1 = a_1b_1+a_2b_2-\alpha = a_3-b_3 = a_1^2+a_2^2+b_1^2+b_2^2-d^2-\beta = 0 . \end{equation*}$$

For any point $(a_1,a_2,a_3)$ in the base such that $(a_1,a_2)\ne (0,0)$, there is a unique point $(b_1,b_2,b_3)$ in the platform and a length such that the motion $C$ keeps the distance of base and platform point equal to $d$. To get the platform point corresponding to a given base point $(a_1,a_2,a_3)$, we invert its projection $(a_1,a_2)$ on the circle with radius $\sqrt {|\alpha |}$ and keep the third coordinate; if $\alpha <0$, then we also have to rotate the projection by an angle of $\pi$.

In the degenerate case $\alpha =\beta =0$, one of the equations of the quartic curve is a perfect square, and the reduced equations $m_{11}^2+m_{12}^2-h^2=x_3$ define a conic in a 2-space. In leg space, we have one less linear equation: $z_{12}-z_{21}=z_{11}+z_{22}=l-2z_{33}=0$, or equivalently

$$\begin{equation*} a_1b_2-a_2b_1 = a_1b_1+a_2b_2 = a_1^2+a_2^2+b_1^2+b_2^2-d^2 = 0 . \end{equation*}$$

Here we get a four-dimensional set of possible legs with two components, namely the set of legs where the platform point or the base point lies on the $z$-axis. The motion is just a revolution around the $z$-axis.

Planar multipods

We consider now the linear subspace $L_p\subset \check{\mathbb{P}}^{16}$ of dimension 9 in the leg space defined by the equations

$$\begin{equation*} a_3=b_3=z_{13}=z_{23}=z_{31}=z_{32} = z_{33}= 0 . \end{equation*}$$

Its intersection $Y_p$ with the leg variety consists of all legs such that the two anchor points lie on a fixed plane. The variety $Y_p$ is the Segre variety $\Sigma _{2,2} \cong \mathbb{P}^2\times \mathbb{P}^2$; let us call its elements informally planar legs. The degree of $Y_p$ is ${2+2\choose 2}=6$.

A multipod such that all its base points are coplanar and all its platform points are coplanar is called a planar multipod (see Figure 14). To obtain the configuration of a planar multipod, one has to intersect the dual space of the linear span of all legs with the group variety $X$. The linear span of the legs is contained in $L_p$, hence the dual space of the linear span contains the dual space $L_p^\bot$. This linear space does not intersect the group variety, otherwise we would have a displacement that preserves the length of all legs in $Y_p$, which is impossible. What we can say is that the projection $\mathbb{P}^{16}\mathrel{\rightdasharrow }\mathbb{P}^9$ with center $L_p^\bot$ projects the group variety to a subvariety $X_p\in \mathbb{P}^9$ of dimension 6 and degree 20 by a map that is generically 2:1. Hence the configurations of a planar multipod come in pairs: for every configuration, there is a conjugated configuration. It can be obtained by an outer automorphism of $\mathrm{SE}_3$, namely the conjugation by the reflection with respect to the plane containing the anchor points.

It is surprisingly easy to construct paradoxically mobile planar hexapods. Here is the reason.

Theorem 5.1 (Duporcq 16).

Let $y_1$, …, $y_5\in Y_p$ be five generic planar legs. Then there exists a planar leg $y_6\in Y_p$ such that the configuration space of the pentapod defined by $(y_1,y_2,y_3,y_4,y_5)$ is equal to the configuration space of the hexapod defined by $(y_1,y_2,y_3,y_4,y_5,y_6)$.

Proof.

Let $V\subset \check{\mathbb{P}}^{16}$ be the linear span of $y_1$, …, $y_5$. Its dimension is $4$. The dimension of $Y_p$ is $5$. Both $V$ and $Y_p$ are contained in $L_p\cong \mathbb{P}^9$, hence the intersection $Y_p\cap V$ is finite. Its cardinality is equal to the degree of $Y_p$, which is 6. We know already five points; we choose $y_6$ to be the sixth.

For both, the pentapod and the hexapod, the configuration set of the pentapod is the intersection of the group variety $X$ with the dual space $V^\bot$. The linear condition imposed by the 6-leg does not impose an independent condition because it lies in the linear span of the other five.

■

Line-symmetric multipods

Another class of paradoxically mobile hexapods is the class of line symmetric hexapods. They can be obtained as special cases of line symmetric moving graphs (see Section 4). The graph consists of two octahedra $G_1,G_2$ together with six edges each joining one point of $G_1$ to one point of $G_2$, so that these six edges provide a graph symmetry between $G_1$ and $G_2$. The automorphism $\tau$ of the whole graph $G$ maps each vertex $v_1$ of $G_1$ to the vertex in $G_2$ connected with the unique vertex in $G_1$ that is not connected with $v_1$ (see Figure 15). This graph automorphism does not fix any vertex or any edge. We fix a line $L$ of symmetry and embed $G$ so that the half turn around $L$ maps each vertex $v$ to the image of $\tau (v)$, generically with respect to this condition. By the count in Section 4, the configurations are solutions of an algebraic system in 16 unknowns and 15 equations, implying mobility.

It pays to analyze the situation again by group-leg duality, following an analysis from 4. Let $L_i\subset \mathbb{P}^{16}$ be the linear subspace in group space defined by the linear equations $M=M^t$ and $x=y$; it intersects $X$ in the subset $X_i$ of all displacement of order 2 or 1. Note that the order 2 elements in $\mathrm{SE}_3$ are exactly the rotations around lines by an angle of $\pi$. These are six equations, hence $\dim (L_i)=10$. The dual subspace $L_i^\bot$ in leg space has dimension 5 and is defined by the equations $l=u=z_ii=a_i+b_j=z_{ij}=0$ for $i$, $j=1$, …, $3$, $i\ne j$. We have a situation that mirrors the planar hexapod case: the subspace $L_i^\bot$ does not intersect the leg variety, otherwise there would be a leg which does not change length in all involutions. But the projection $\check{\mathbb{P}}^{16}\mathrel{\rightdasharrow }\check{\mathbb{P}}^{10}$ with center $L_i^\bot$ projects the leg variety $Y$ to a subvariety $Y_i\in \check{\mathbb{P}}^{10}$ of dimension 7 and degree 10 by a map that is generically 2:1. Hence the legs of a multipod with involutive displacements come in pairs: if $(a,b,d)$ is a leg, then $(b,a,d)$ is also a leg. This can also be shown directly: if $\sigma \in \mathrm{SE}_3$ has order 2, then

$$\begin{equation*} ||\sigma (a)-b|| = ||\sigma ^2(a)-\sigma (b)|| = ||\sigma (b)-a|| . \end{equation*}$$

Group-leg duality induces a duality between the projective subspace $L_i$ of dimension 10 that contains $X_i$ and the projective image space $\check{\mathbb{P}}^{10}$ that contains $Y_i$. Let us call the elements in $Y_i$ twin pairs of legs; each such pair of legs is constituted by a leg $(a,b,d)$ and by its conjugated leg $(b,a,d)$. Generically, three twin pairs in $Y_p$ correspond to three hypersurfaces in $L_i$. Since $\dim (X_i)=4$, the intersection of these three hypersurfaces and $X_p$ is a curve. So, we have explained again the paradoxical mobility.

But there is more. We have not just constructed a mobile hexapod, we have even constructed, at the same time, a mobile icosapod! Here is the precise statement.

Theorem 5.2.

Let $p_1,p_2,p_3$ be three generic twin pairs of legs. Let $C\subset X_s$ be the configuration curve of the hexapod defined by all six legs. Then there exist seven additional twin pairs, maybe complex, such that $C$ is the set of all order $2$ displacements compatible with all $20$ legs.

Proof.

The three twin pairs span a generic 2-plane in $V\subset \check{\mathbb{P}}^{10}$. The subvariety $Y_i\subset \check{\mathbb{P}}^{10}$ has dimension 7, hence $V$ and $Y$ intersect in $\deg (Y_i)=10$ points. Three of them correspond to $p_1,p_2,p_3$, and the remaining seven are the additional pairs we require. The linear span of all ten points is equal to the linear span of $p_1,p_2,p_3$, namely $V$, hence the conditions for displacements do not change.

■

In 18 it is shown that there exist examples where all $20$ legs are real. The proof is based on a result on quartic spectahedra in 1138.

6. Compactification

In enumerative algebraic geometry, for instance for the problem of counting rational curves on a projective variety, compactifications of moduli spaces are known as a powerful tool. Here, we compactify the algebraic varieties in which the configuration spaces are naturally embedded: products of subgroups of $\mathrm{SE}_3$ in the case of linkages with revolute joints, $\mathrm{SE}_3$ itself in the case of multipods, and products of the plane in the case of moving graphs.

6.1. Moving graphs

In Section 2, we saw that if a graph $(V,E)$ has NAC coloring, then it also has a flexible labeling. Here we use compactification to prove the converse, too. The proof is taken from 23.

Theorem 6.1.

A graph $(V,E)$ has a flexible labeling $\lambda$ if and only if it has NAC coloring.

For example, the graph in Figure 16 has no NAC coloring and therefore never moves for any labeling $\lambda$.

Let $(V,E,\lambda )$ be a graph with an edge assignment. We would like to projectivize in order to compactify; for this purpose, it is convenient to change the notion of a configuration slightly. A homogeneous configuration is an assignment of vertices by points in $\mathbb{R}^2$ such that for any two edges $e=(i,j)$, $f=(k,l)$, the equality

$$\begin{equation*} \lambda _e ||p_k-p_l||^2 = \lambda _f ||p_i-p_j||^2 \end{equation*}$$

holds. For each vertex $k\in V$ with assigned point $p_k$, we write $p_k=(x_k,y_k)$ and $z_k\coloneq x_k+\mathrm{i} y_k$, $w_k\coloneq x_k-\mathrm{i} y_k$. In other words, the complex numbers $z_1$, …, $z_{|V|}$ represent the vertices in the Gaussian plane of complex numbers. In order to normalize, we require $p_1=(0,0)$.

The homogeneous configuration $p$ defines a point in $\mathbb{P}^{|V|-2}\times \mathbb{P}^{|V|-2}$ as follows: its first component has projective coordinates $(z_2:\dots :z_{|V|})$, and its second component has coordinates $(w_2:\dots :w_{|V|})$. The equality above reads

$$\begin{equation} \lambda _e (z_k-z_l)(w_k-w_l) - \lambda _f (z_i-z_j)(w_i-w_j) {\tag{6}} \end{equation}$$

in these projective coordinates. This is a bihomogeneous equation of bidegree $(1,1)$. The set of all solutions of 6 is a projective subvariety of $\mathbb{P}^{|V|-2}\times \mathbb{P}^{|V|-2}$, the configuration variety of $(V,E,\lambda )$. Equivalent homogeneous configurations define the same point in the configuration variety: since we fixed $p_1=(0,0)$, equivalent configurations are related by a rotation or a scaling; but such a transformation just multiplies all $z$-coordinates by a complex nonzero constant and all $w$-coordinates by a different complex nonzero constant, hence does not change the points in $\mathbb{P}^{|V|-2}$.

A point $\alpha \in \mathbb{P}^{|V|-2}\times \mathbb{P}^{|V|-2}$ corresponds to a homogeneous configuration if and only if it fulfills two extra conditions. First, the conjugate has to coincide with the flip of the first and second component; if this condition fails, then some of the corresponding points in the plane have nonreal coordinates. Second, for some edge $e=(i,j)$, we have $(z_i-z_j)(w_i-w_j)\ne 0$. By 6, the choice of the edge has no influence on the validity of this extra condition.

The boundary of the configuration set is defined as the set of points in the configuration variety that fail to satisfy the two extra conditions. In particular, for some edge $e=(i,j)$, or equivalently for all edges, we have $(z_i-z_j)(w_i-w_j)=0$. For each point $\beta$ in the boundary, we define a coloring of the edges of the graph in the following way: the edge $(i,j)$ is colored red if $z_i-z_j$ vanishes at $\beta$, and it is blue otherwise.

Lemma 6.2.

For any point $\beta$ in the boundary of the configuration variety, the coloring defined by it is NAC coloring.

Proof.

Assume, for the sake of contradiction, that all edges are red. Then the first projection of $\beta$ to $\mathbb{P}^{|V|-2}$ has only zero coordinates, which is impossible.

Assume, for the sake of contradiction, that all edges are blue. For any edge $(i,j)$, we have $(z_i-z_j)(w_i-w_j)=0$ and $z_i-z_j\ne 0$. It follows that the second projection of $\beta$ to $\mathbb{P}^{|V|-2}$ has only zero coordinates, which is impossible.

Assume, for the sake of contradiction, that $(i_1,\dots ,i_k,i_1)$ is cycle such that $(i_r,i_{r+1})$ is red for all $r=1$, …, $k-1$, and $(i_k,i_1)$ is blue. Then $z_{i_1}=\dots =z_{i_k}$ and $z_{i_k}\ne z_{i_1}$, which is impossible.

Assume, for the sake of contradiction, that $(i_1,\dots ,i_k,i_1)$ is cycle such that $(i_r,i_{r+1})$ is blue for all $r=1$, …, $k-1$, and $(i_k,i_1)$ is red. Then $w_{i_1}=\dots =w_{i_k}$, hence $w_{i_k}=w_{i_1}$. In addition, we also have $z_{i_k}=z_{i_1}$ as $(i_k,i_1)$ is red. Therefore the form $(z_{i_1}-z_{i_k})(w_{i_1}-w_{i_k})$ vanishes with order $m\ge 2$ at $\beta$. The order of this form is the same for every edge, and because $(i_r,i_{r+1})$ is blue, the forms $z_r-z_{r+1}$ have order $0$ for $r=1$, …, $k-1$. Hence the order of the forms $w_r-w_{r+1}$ is at least $m$, for all $r$. Then the form $w_{i_1}-w_{i_k}$ vanishes with order at least $m$, and this is a contradiction.

■

Proof of Theorem 6.1.

If $(V,E,\lambda )$ is flexible, then its configuration set is a projective variety $K$ of positive degree in $\mathbb{P}^{|V|-2}\times \mathbb{P}^{|V|-2}$. For any edge $(i,j)\in E$, the form $(z_i-z_j)(w_i-w_j)$ has to vanish somewhere in $K$. Therefore, $K$ meets the boundary. By Lemma 6.2, it follows that $(V,E)$ has NAC coloring.

Conversely, assume that we have NAC coloring of the edges. Then we make the graph moving by a construction given in Section 1: the red edges always keep their direction and move by translations only, while the blue edges rotate with uniform speed.

■

A weakness of Theorem 6.1 is that its constructive part—the construction of flexible labelings—produces only a particular type of motions that we may call uniform speed motions. Also, these motions sometimes map different nonadjacent vertices to the same point in the plane. For example, in the case of the complete bipartite graph $K_{3,3}$, all uniform speed motions map at least two pairs of vertices to the same point in the plane, and the moving graph looks like a moving parallelogram. Deciding if a given graph has labeling with a generically injective motion is much harder than deciding the existence of a flexible labeling; see 24.

6.2. Revolute loops

The complete classification of mobile 4R loops was given by Delassus (see Section 3). The complete classification of mobile 5R loops was given in 29 with the help of computer algebra. For 6R loops, the classification is still open; the difficult part is to come up with necessary conditions for mobility. In this subsection, we will give necessary criteria for mobility of $n$R loops, where $n=4,5,6$.

Let $d_1$, …, $d_n$ (normal distances), $s_1$, …, $s_n$ (offsets), and $\alpha _1$, …, $\alpha _n$ (angles) the invariant Denavit/Hartenberg parameters; we assume that none of the angles is $0$ or $\pi$. For $r=0$, …, $n-1$, we set $w_r=\cot (\alpha _r/2)$, $c_r\coloneq \cos (\alpha _r)$, and $b_r\coloneq \frac{d_r}{\sin (\alpha _r)}$. Then we define the $2n$ complex quadratic polynomials

$$\begin{equation*} \begin{split} Q_r^{\pm }(x) &= \left(x+\frac{b_{r+2}c_{r+2}-b_rc_r}{2}-\frac{s_r}{2}\mathrm{i}\right)^2\\ &\quad + \frac{\mathrm{i}}{2}\left(b_r s_{r+1} \pm b_{r+2} s_{r+2} \pm s_{2} b_{r+2} c_{r+1}+s_{r+2} b_r c_{r+1}\right)\\ &\quad -\frac{ -s_{r+1} s_{r+2} c_{r+1} \pm b_r b_{r+2} c_{r+1} }{2}\\ &\quad +\frac{s_{r+1}^2+s_{r+2}^2-b_r^2+b_{r+1}^2-b_{r+2}^2-b_{r+1}^2 c_{r+1}^2}{4}\\ &\in \mathbb{C}[x], \end{split} \end{equation*}$$

where the indices are understood modulo $n$.

Theorem 6.3.

If the $n\mathrm{R}$ loop with invariant Denavit/Hartenberg parameters is mobile, then one of the following conditions holds.

(1)

There exists $r\in \{0,\dots ,n-1\}$ such that $b_r=\pm b_{r+1}$ and $s_r=0$.

(2)

We have $n=6$, and for $r=0$, $1$, $2$, the polynomials $Q^+_r$ and $Q^+_{r+3}$ have a common zero, or the polynomials $Q^-_r$ and $\overline{Q^-_{r+3}}$ have a common zero; here, $\overline{Q^-_{r+3}}$ is the complex conjugate of $Q^-_{r+3}$.

In order to derive one of these conditions, we express the closure equation in a more algebraic way, using dual quaternions. For $r=0$, …, $n-1$, the dual quaternion $g_r \coloneq (1-s_r\epsilon \mathbf{i})(w_r-\mathbf{k})(1-d_i\mathbf{k})$ is the displacement that transforms the internal coordinate system of link $r$ to the internal coordinate system of link $r+1$ (modulo $n$), if the configuration parameter is $0$. The closure equation is an equation in the variables $t_0$, …, $t_{n-1}$, which denote the cotangents of the half configuration angles: the dual quaternion

$$\begin{equation*} x(t_0,\dots ,x_{n-1}) \coloneq (t_0-\mathbf{i} )g_0(t_1-\mathbf{i} )g_1\cdots (t_{n-1}-\mathbf{i} )g_{n-1} \end{equation*}$$

is a multiple of $1$, hence seven of its eight coefficients are $0$. The variables $t_0$, …, $t_{n-1}$ may also assume the value $\infty$; in this case, the corresponding factor $(t_r-\mathbf{i})$ is replaced by the scalar 1, or is simply omitted. In this section, we will avoid this technicality.

We focus on solutions on the boundary, but this time we do not consider $t_r=\infty$ as boundary. Instead, we define the boundary of $(\mathbb{P}^1)^n$ as the set of $n$-tuples $(t_0,\dots ,t_{n-1})$ such that $t_r^2+1=0$ for at least one $r$. Indeed, if we remove the boundary, then we get a group variety isomorphic to $(\mathrm{SO}_2)^n$, with an isomorphism respecting real structures. The statement that $t_r^2+1=0$ for at least one $r$ is equivalent to the statement $N(x(t_0,\dots ,t_n))=0$, by the multiplicativity of the norm. Boundary solutions can never be real; at least one of the variables must be equal to $\pm \mathrm{i}$.

Note. Throughout this paper, we use $\mathbf{i}$ for the first quaternion unit in $\mathbb{H}$, $\mathrm{i}$ for the imaginary unit in $\mathbb{C}$, and $i$ for a running integer. In this section, both $\mathbf{i}$ and $\mathrm{i}$ will appear, sometimes in the same expression, but we will try to avoid using $i$ for an integer.

Unfortunately, the closure equation often has many solutions that are not of interest. But we can obtain more equations by cyclic permutation of its factors, or by using quaternion conjugation to bring some factors to the other side, as in

$$\begin{equation*} \lambda (t_0-\mathbf{i})g_0= \nu \overline{g_{n-1}}(t_{n-1}+\mathbf{i})\overline{g_{n-2}}\cdots \overline{g_1}(t_1+\mathbf{i}) \end{equation*}$$

for some scalars $\lambda ,\nu$ that are not both equal to $0$. This condition can be expressed by polynomial equations, namely the $2$-minors of the $2\times 8$ matrix whose rows are the coordinates of $(t_0-\mathbf{i})g_0$ and of $\overline{g_{n-1}}(t_{n-1}+\mathbf{i})\overline{g_{n-2}}\cdots \overline{g_1}(t_1+\mathbf{i})$. After having added all these reformulations of the closure equations to our system of equations, we look for solutions on the boundary. These are called bonds.

We leave it as an exercise to prove that at least two of $t_0$, …, $t_{n-1}$ must be $\pm \mathrm{i}$. Hint. Use a formulation of the closure equation with factors on both sides, and then take the norm on both sides. There are many examples with exactly two of $t_0$, …, $t_{n-1}$ being $\pm \mathrm{i}$. If, say, $t_1^2+1=t_k^2+1=0$ for some $k<n$, and $t_i^2+1\ne 0$ for $i\ne 1,k$, then we say that the first joint and the $k$th joint are entangled in the respective bond. We can then prove the following equations:

$$\begin{equation} \begin{aligned} (t_1-\mathbf{i} )g_1(t_2-\mathbf{i})g_2\cdots (t_k-\mathbf{i} ) = 0, \\ (t_k-\mathbf{i} )g_k(t_{k+1}-\mathbf{i})g_{k+1}\cdots (t_0-\mathbf{i} )g_n(t_1-\mathbf{i} ) = 0. \end{aligned} {\tag{7}} \end{equation}$$

If the number of coordinates $t_r$ with $t_r^2+1=0$ is bigger than $2$, then equation 7 also holds for some $k>1$, up to cyclic permutation, by 26, Lemma 2 and Theorem 3.

Equation 7 together with $t_1^2+1=t_k^2+1=0$ is quite restrictive and often has implications on the invariant parameters that are hard-coded in $g_0$, …, $g_{n-1}$. The case $k=2$ can be dismissed as follows. Assume

$$\begin{equation*} (\mathrm{i}-\mathbf{i})g_1(\mathrm{i}-\mathbf{i}) = 0 . \end{equation*}$$

Then it follows that $w_1=d_1=0$; geometrically this means that the first two rotation axes are equal, except that they have opposite orientation in the closure equation. This degenerate case contradicts our assumption that none of the angles is $0$ or $\pi$; and so, we always have $k>2$ (and modulo $n$, this also excludes $k=0$).

If $k=3$, then we get the equation

$$\begin{equation*} (\mathrm{i}-\mathbf{i})g_1(t_2-\mathbf{i})g_2(\mathrm{i}-\mathbf{i}) = 0, \end{equation*}$$

up to orientation of the first and/or third axis. This is a system of inhomogeneous linear equations for $t_2$. It has a solution in three cases: either the three axes are parallel, or the three axes are concurrent, or the equations

$$\begin{equation*} s_1=0, b_1=b_2 \end{equation*}$$

are true. This is almost equal to condition $(1)$ in Theorem 6.3, for $r=1$. If we put the opposite orientation on the third axis, we obtain $s_1=0$ and $b_1=-b_2$. Compare also with Bennett’s condition for the mobility of a 4R loop in Section 3.

The analysis of the case $k=4$ is more involved; however, it is necessary in order to explain mobility of 6R linkages in which no three consecutive axes fulfill the Bennett condition. Assume that $n=6$, and we have a bond $\vec{t}$ that entangles the first and fourth joints. Without loss of generality, we may assume $t_1=t_4=\mathrm{i}$. Then we obtain the equations

$$\begin{equation} \begin{aligned} (\mathrm{i}-\mathbf{i})g_1(t_2-\mathbf{i})g_2(t_3-\mathbf{i})g_3(\mathrm{i}-\mathbf{i}) = 0, \\ (\mathrm{i}-\mathbf{i})g_4(t_5-\mathbf{i})g_5(t_0-\mathbf{i})g_0(\mathrm{i}-\mathbf{i}) = 0. \end{aligned} \tag{8} \end{equation}$$

Excluding some degenerate cases (four parallel lines or four lines meeting in a point), the first equation allows two solutions for $(t_2,t_3)$, while the second equation allows two solutions for $(t_0,t_5)$. These partial solutions are not independent. They have to satisfy another reformulation of the closure equation

$$\begin{equation*} \lambda (\mathrm{i}-\mathbf{i})g_1(t_2-\mathbf{i})g_2(t_3-\mathbf{i})g_3 = \nu \overline{g_0}(t_0+\mathbf{i})\overline{g_5}(t_5+\mathbf{i})\overline{g_4}(\mathrm{i}+\mathbf{i}) \end{equation*}$$

for some complex numbers $\lambda ,\nu$ that are not both equal to $0$. In 33, it is shown that the dual quaternions on both sides of the equations above have to be of the form $(1+x\epsilon )(\mathbf{j}+\mathrm{i}\mathbf{k})$, where $x\in \mathbb{C}$ is a common zero of the polynomials $Q^+_1$ and $Q^+_4$. In particular, these two polynomials do have a common complex zero.

If $t_1=\mathrm{i}$ and $t_4=-\mathrm{i}$, then the polynomials $Q^-_1$ and $\overline{Q^-_4}$ have a common zero; this is shown in a similar way.

Proof of Theorem 6.3.

If $n=4$ or $n=5$, then we necessarily have two entangled joints that have exactly one joint between them, in the cyclic order of joints. In the above discussion, we can reduce to the case $k=2$, which shows the first condition.

If $n=6$ and only “opposite” joints are entangled, i.e., zeroth and third, first and fourth, second and fifth, then we reduce to the case $k=3$. In this case, 33 shows that all three opposite pairs of opposite joints are entangled.

■

Suppose that we have the maximal number of eight bonds entangling opposite axes, for all three pairs of opposite axes. This assumption leads to a system of algebraic equations in the invariant Denavit/Hartenberg parameters (18 variables). Using computer algebra, we can compute the solution set (see 33). It turns out that there are two components $F_1$ and $F_2$, of dimensions 6 and 7, respectively. Both are families of mobile 6R loops that were unknown before bonds were used in kinematics. But the family $F_1$ (the one of dimension 6) has a five-dimensional subfamily which is classical: Bricard’s orthogonal 6R loops, characterized by the vanishing of $c_0$, …, $c_5$ (i.e., all angles are right angles) and $s_0$, …, $s_5$ (i.e., all offsets are $0$), and the single equation $b_0^2-b_1^2+b_2^2-b_3^2+b_4^2-b_5^2=0$.

6.3. Multipods

This subsection contains a necessary condition for a multpod to be mobile. We assume that the leg set of the multipod is equal to $\{ (a_l,b_l,d_l) \mid l\in L\}$, where $L$ is an index set, $a_l\in \mathbb{R}^3, l\in L$ are the anchor points at the base, $b_l\in \mathbb{R}^3, l\in L$ are the anchor points at the platform, and $d_l\in \mathbb{R}^3, l\in L$ are the leg lengths. Our condition is a geometric condition on the anchor points; it does not depend on the leg lengths.

In order to explain the geometric condition, we need to recall the following two geometric concepts.

•

An orthogonal projection is a surjective linear map $p:\mathbb{R}^3\to \mathbb{R}^2$ that maps the plane orthogonal to the kernel isometrically to the image plane.

•

The group $M$ of inversive transformations from $(\mathbb{R}^2\cup \{\infty \})$ to itself is generated by inversions at circles, direct isometries, and similarity transformations. It is also known as the group of Möbius transformations.

It is well known that $M$ is a Lie group of dimension 6, isomorphic to the complex projective group $\mathrm{PGL}_2(\mathbb{C})$.

Theorem 6.4.

If a multipod with leg set $\{ (a_l,b_l,d_l) \mid l\in L\}$ is mobile, then one of the following conditions is true.

(1)

There exist orthogonal projections $p_a:\mathbb{R}^3\to \mathbb{R}^2$ and $p_b:\mathbb{R}^3\to \mathbb{R}^2$ and an inversive transformation $m:\mathbb{R}^2\to \mathbb{R}^2$ such that $m(p_a(a_l))=p_b(b_l)$ for all $l\in L$.

(2)

There exist lines $G_a, G_b\in \mathbb{R}^3$ such that $a_l\in G_a$ or $b_l\in G_b$ for all $l\in L$.

Recall the Bricard/Borel multipod with infinitely many legs, described in Section 5. All its legs $(a,b,d)$ satisfy the condition

$$\begin{equation*} a_1b_2-a_2b_1 = a_1b_1+a_2b_2-\alpha = 0 \end{equation*}$$

for some fixed $\alpha \in \mathbb{R}$, $\alpha \ne 0$. Here, condition (1) is fulfilled: $p_a$ and $p_b$ are both the orthogonal projection to the first two coordinates, and $m$ is the inversion at a circle with radius $\sqrt {|\alpha |}$, followed by a point reflection in case $\alpha <0$.

Condition (2) is equivalent to the existence of a partition of the set of legs into two subsets, with the first subset having collinear anchor points in the base and the second subset having collinear anchor points in the platform. Let us called such a configuration a combined collineation. The existence of such a combined collineation already implies mobility for a suitable choice of leg lengths. To see this, we start with a configuration such that the lines $G_a$ and $G_b$ coincide—the leg lengths have to chosen so that such a configuration exists. Then we can rotate the platform around this line (similar as the double banana in Figure 4).

In order to prove Theorem 6.4, we compactify the group variety $X\in \mathbb{P}^{16}$. The boundary of $X$ is defined as the intersection of $X$ with the hyperplane $H:h=0$, with the variable set as in Section 5. In 20 it is shown that $B$ is a variety of dimension 5 and degree 20. The variety $X$—which has degree 20—and the hyperplane $H$ intersect tangentially along $B$, with intersection multiplicity 2. It is defined by the equations

$$\begin{equation*} M M^t = M^t M = \mathrm{adj}(M) = Mx = M^t y = 0 ; \end{equation*}$$

here the projective coordinates are the entries of $M\in \mathbb{C}^{3\times 3}$ and $x,y\in \mathbb{R}^3$ together with $r$ and $h$ (which is $0$). The condition $\mathrm{adj}(M)=0$ is equivalent to $\mathrm{rank}(M)\le 1$. The boundary has only a single real point, with $r=1$ and $M$, $x$, $y$, and $h$ being $0$.

Sketch of proof of Theorem 6.4.

The projective closure of the configuration has to intersect the hyperplane $H$ somewhere on the boundary. If $\beta$ is the intersection point, then the dual hyperplane $\beta ^\ast$ in leg space must contains all legs of the multipod. The analysis in 20 of the boundary shows that the claim follows. We illustrate this by two examples.

First, assume that $\beta$ is given by

$$\begin{equation*} \begin{split} &(m_{11}:\dots :m_{33}:x_1:x_2:x_3:y_1:y_2:y_3:r:h)\\ &\qquad = (1:\mathrm{i}:0:\mathrm{i}:-1:0:0:0:0:0:0:0:2:0). \end{split} \end{equation*}$$

Then the dual hyperplane $\beta ^\ast$ has equation $-2z_{11}+2z_{22}+2u - 2\mathrm{i}(z_{12}+z_{21}) = 0$. We claim that condition (1) is fulfilled. Let $p_a,p_b:\mathbb{R}^3\to \mathbb{R}^2$ be the projection to the first two coordinates, and let $m:\mathbb{R}^2\to \mathbb{R}^2$ be the inversive transformation $(u,v)\mapsto \left(\frac{u}{u^2+v^2},\frac{-v}{u^2+v^2}\right)$. Let $((a_1,a_2,a_3),(b_1,b_2,b_3),d)$ be a leg. It corresponds to a real point in leg space contained in $\beta ^\ast$. Both the real part and the imaginary part of the linear form defining $\beta ^\ast$ have to vanish, so we get

$$\begin{equation*} -2a_1b_1+2a_2b_2+2 = 2a_1b_2+2a_2b_1 = 0 . \end{equation*}$$

This is equivalent to the statement $m((a_1,a_2))=(b_1,b_2)$.

Second, assume that $\beta$ is given by

$$\begin{equation*} \begin{split} &(m_{11}:\dots :m_{33}:x_1:x_2:x_3:y_1:y_2:y_3:r:h) \\ &\qquad = (1:\mathrm{i}:0:\mathrm{i}:-1:0:0:0:0:0:0:0:0:0). \end{split} \end{equation*}$$

Then the dual hyperplane $\beta ^\ast$ has equation $-2z_{11}+2z_{22} - 2\mathrm{i}(z_{12}+z_{21}) = 0$. We claim that condition (2) is fulfilled, with both lines $G_a,G_b\in \mathbb{R}^3$ being equal to the third axis. If $((a_1,a_2,a_3),(b_1,b_2,b_3),d)$ is a leg, then the fact that the corresponding real point in leg space is contained in $\beta ^\ast$ implies the equation

$$\begin{equation*} -2a_1b_1+2a_2b_2 = 2a_1b_2+2a_2b_1 = 0 , \end{equation*}$$

which is fulfilled if and only if $a_1=a_2=0$ or $b_1=b_2=0$.

■

For many mobile multipods, the curve of configurations intersects the hyperplane in several points. The number of intersection points is related to the degree of the configuration curve embedded in $\mathbb{P}^{16}$. The correlation between the degree of the mobility curve of a hexapod and the number of special geometric events (projections related by an inversive transformation, or combined collineations) motivates the question on the maximal number of such events. Here are the answers.

Theorem 6.5.

Assume that the six-tuple of points in the base and the six-tuple of points in the platform are not similar, and that neither the base nor the platform consist of coplanar points.

(a)

The number of combined collineations is at most $16$. If every anchor point appears in at most one leg, for both base and platform, then the maximal number of combined collineations is $4$.

(b)

The number of orthogonal projections related by an inversive transformations is at most $7$.

The proof of (a) is left as an exercise. For the proof of (b), we refer to 21.

It is conjectured in 21 that for a generic choice of six points in $\mathbb{R}^3$, there exists a second six-tuple of points, such that the maximal number of seven projections related by an inversion is reached; such a six-tuple would then be unique up to similarity. The conjecture continues to state that there is a unique scaling and choice of leg length such that the so-constructed hexapod is mobile, with a mobility curve of maximal degree 28. For a numeric random choice, the conjecture can be tested by a construction taking about 300 seconds using computer algebra. Using this construction, the conjecture has been verified for 50 random choices. Theoretically, it is still possible that these 50 random choices were picked on some unknown subvariety with nongeneric behavior, but it is quite unlikely.

7. Open problems

Generic hexapods are rigid. The subset of mobile hexapods in $(\mathbb{R}^3\times \mathbb{R}^3\times \mathbb{R})^6$ is semialgebraic, so we know that there exists a description by algebraic equations and inequalities. Its Zariski closure—defined only by equalities—is a reducible algebraic variety which we do not understand very well. How many irreducible components does it have? What is the dimension of each of the irreducible components? Are the components unirational? If we could answer these questions, then we could say we have classified mobile hexapods. Now, we have only partial answers, some of them are more than 100 years old (Bricard and Borel, see Section 5). There is no prize money any more, but the classification of mobile hexapods is still a challenge.

Another old open question has been mentioned in Subsection 6.2: the classification of mobile 6R loops. The situation is analogous: the subset of mobile 6R loops in $\mathbb{R}^{18}$ is semialgebraic, and its Zariski closure is a reducible algebraic variety which we do not understand very well. In the kinematics literature 114, there are lists of known families, meaning irreducible algebraic varieties contained in our big unknown variety. Some of them are irreducible components, and at least one other known family has turned out to be properly contained in an irreducible component (see the last paragraph of Section 3).

In rigidity theory, the open problem which is discussed most is to find a three-dimensional analogue for Theorem 1.3. The paper 28 mentions a complete algorithmic criterion and several partial combinatorial criteria. My own favorite problem is to find a three-dimensional analogue for Theorem 6.1, aiming at a combinatorial criterion for the existence of a flexible length assignment. M. Gallet, G. Grasegger, J. Legersky, and I are currently studying 1-skeletons of convex triangular polyhedra, and it could be that we have found an interesting necessary criterion for this subcase—we will let you know!

Figure 1.

A mechanism that is able to draw an ellipse. The short gray horizontal bar is fixed on the $x$-axis, whereas all the other bars are allowed to move, according to the rotational joints which link them one to another.

Figure 2.

A hinge (revolute joint), a hip joint (spherical), and a trolley on a crane (prismatic joint)

Figure 4.

The smallest graph that is generically mobile and still fulfills the three-dimensional analogue of Laman’s condition for generic rigidity: $3|V|-6=|E|$, and $3|V'|-6\ge |E'|$ for every subgraph $(V',E')$. The blue part may revolve around the line through two vertices.

Figure 5.

A kinematic model of the Methoxyethanol molecule $\mathrm{C}_3\mathrm{H}_6(\mathrm{OH})_2$. The cylinders are joints allowing a rotation around the central axis of the cylinder. Note that the axis always passes through the centers of the joined atoms.

Figure 6.

A mobile complete bipartite graph $K_{4,4}$. Its points form two rectangles sharing their symmetry axes.

Figure 7.

A mobile graph with NAC coloring. The blue edges remain parallel to the original orientation, and the orientation of the red edges rotates with speed that is independent of the edge, as long as it is red.

Figure 8.

A moving Laman graph with eight vertices and 13 edges. These two figures are 2D not 3D! To see this picture correctly, please switch off your spatial perception for a moment. They show two of infinitely many possible configurations of the graph in $\mathbb{R}^2$, with the same edge lengths. Every edge is parallel to one of the four sides of the red quadrilateral. The red quadrilateral has infinitely many configurations: any configuration of the red quadrilateral can be extended to a configuration of the whole graph.

Figure 9.

A thumbnail movie of a mobile 6R loop. Each of the six links is realized as a tetrahedron. Each tetrahedron has two edges, opposite to each other, playing the role of R-joints (hinges) connecting the link to its two neighbors. The grey tetrahedron is not moving.

Figure 10.

The windshield wiper in (a) consists of two planar 4R loops that have two links in common: one common link is the wheel in the center driven by a motor. The second common link is the window. The picture is taken from http://en.wikipedia.org/wiki/Windscreen_wiper. The spherical 4R loop in (b) occurs in paper folding/origami: four creases meeting in a point play the roles of the rotation axes (hinges).

Figure 11.

The skew isogram is a mobile 4R loop, so that the rotation axes in the same link are always skew. It is the only mobile 4R loop which is neither planar (all axes are parallel) nor spherical (all axes are concurrent).

Figure 12.

This graph displays different factorizations of equal products in the polynomial ring of dual quaternions. For any two directed paths between two vertices, the two products of the linear polynomials appearing as edge labels in each path are equal. The dual quaternions $h_0$, …, $h_9$ are defined as follows: $h_0=2\mathbf{k}+d\epsilon \mathbf{j}$, $h_1=\mathbf{k}-(a/2+b/2)\epsilon \mathbf{j}$, $h_2=\mathbf{k}-(-a/2+b/2-c)\epsilon \mathbf{j}$, $h_3=-\mathbf{k}-\epsilon c\mathbf{j}$, $h_4=\mathbf{k}+\frac{a+b+4d}{6}\epsilon \mathbf{j}$, $h_5=2\mathbf{k}+\frac{-2a-2b+d}{3}\epsilon \mathbf{j}$, $h_6=\mathbf{k}+\frac{-11a-5b-6c+4d}{18}\epsilon \mathbf{j}$, $h_7=2\mathbf{k}+\frac{4a-8b+12c+d}{\epsilon }\mathbf{j}$, $h_8=-\mathbf{k}+\frac{-8a+16b+3c-2d}{9}\epsilon \mathbf{j}$, $h_9=2\mathbf{k}+\frac{4a-8b+d}{3}\epsilon \mathbf{j}$. Here, $a$, $b$, $c$, $d$ are arbitrary real constants.

$$\begin{equation*} \vcenter{\img[][249pt][61pt][{$\xymatrix{ \circled{1} \ar^{t-h_1}[rr] &amp; &amp; \circled{2} \ar^{t-h_2}[rr] &amp; &amp; \circled{3} \ar^{t-h_3}[rr] &amp;&amp; \circled{4} \\ \circled{5} \ar^{t-h_4}[rr] \ar^{t-h_0}[u] &amp;&amp; \circled{6} \ar^{t-h_6}[rr] \ar^{t-h_5}[u] &amp; &amp; \circled{7} \ar^{t-h_8}[rr] \ar^{t-h_7}[u] &amp;&amp; \circled{8} \ar^{t-h_9}[u] }$}]{Images/img08d5119a6f01dee416a99d36a8301187.svg}} \end{equation*}$$

Figure 13.

The left side shows a flexible octahedron that is symmetric by a line reflection. The right side shows a flexible octahedron that is symmetric by a plane reflection. Corresponding edges are shown in the same color.

Figure 14.

A planar hexapod. For any configuration, there is also a conjugated configuration that can be obtained by reflection on the green base plane.

Figure 15.

A graph consisting of two octahedra and six additional edges with a graph automorphism of order 2 that does not fix any vertex or any edge. The automorphism is shown by vertex orbits: conjugated vertices have equal labels. By symmetric counting of variables and equations, a generic line symmetric embedding does move. In this motion, the two octahedra are rigid, and we obtain a mobile hexapod.

Figure 16.

A graph that does not have NAC coloring. Consequently, the graph is rigid for every possible labeling of its edges.