---
abstract: 'We prove that every bounded rational space curve of degree $d$ and circularity $c$ can be drawn by a linkage with $ \frac{9}{2} d-6c+1$ revolute joints. Our proof is based on two ingredients. The first one is the factorization theory of motion polynomials. The second one is the construction of a motion polynomial of minimum degree with given orbit. Our proof also gives the explicit construction of the linkage.'
address:
- 'Joanneum Research, Institute for Robotics and Mechatronics, Lakeside B08a, 9020 Klagenfurt, Austria, Phone +43 316 876 2016'
- 'Research Institute for Symbolic Computation, Johannes Kepler University Linz, Schloss Hagenberg, 4232 Hagenberg, Austria'
- 'Unit Geometry and CAD, University of Innsbruck, Technikerstr. 13, 6020 Innsbruck, Austria'
author:
- Zijia Li
- Josef Schicho
- 'Hans-Peter Schröcker'
title: |
    Kempe’s Universality Theorem\
    for Rational Space Curves
---

Introduction {#sec:introduction}
============

Kempe’s Universality Theorem [@kempe76] is one of the great theorems of theoretical mechanism science (“beautiful” [@blaschke56; @demaine07], “surprising” [@abbott08; @demaine07], “incredible theoretical significance” [@saxena11], “shocking” [@gao01]). It states that any bounded portion of a planar algebraic curve can be traced out by one joint of a planar linkage with revolute joints. Discovered only shortly after the invention of the first straight line linkages, Kempe’s theorem must have been a true surprise to his contemporary kinematicians. Throughout the 20th century, it was considered a milestone result.

Kempe’s constructive proof can be used to actually compute a linkage that draws a planar algebraic curve. However, it was clear from the beginning that this construction is of no practical relevance. It requires an excessive number of links and joints, even for curves of low degree. Nowadays, an asymptotic bound of $O(d^n)$ for the number of links necessary to draw an algebraic curve of degree $d$ in an ambient space of dimension $n$ is known [@abbott08]. Nonetheless, drawing an ellipse with a Kempe linkage already requires hundreds of links [@kobel08]. A wealth of more practical examples for algebraic curve generation can be found in the monograph [@artobolevskii64]. However, the constructions there are rather specific to certain classes of curves and, more importantly, use mechanical constraints different from rigid links and revolute joints.

Kempe’s Theorem talks about algebraic curves and it is natural to ask for simplifications in case of rational curves. This was done recently in [@gallet15] where the authors constructed scissor-like linkages to draw rational planar curves. Their construction is based on the factorization of certain polynomials over a non-commutative ring that describe the motion of one of the links. The upper bounds on the number of links and joints for curves of degree $d$ reduce dramatically to $3d+2$ and $\frac{9}{2}d+1$, respectively. In this article, we extend the ideas of [@gallet15] to rational space curves. Our aim is to provide a construction that works for all rational space curves and, at the same time, to reduce the number of links and joints as far as possible. For this purpose, we introduce several new ideas that also improve the planar case.

We use rational motions of minimal degree in the dual quaternion model of rigid body displacements for the link that draws the given space curve. This acknowledges the importance of circularity. If the rational space curve is entirely circular, the motion degree is particularly low [@li15b; @li15a] and factorization of the motion polynomial is straightforward, without the need for prior degree elevation. In the non-circular case, a degree elevation is necessary but in contrast to [@gallet15; @li15b], we only preserve one relevant trajectory, not the complete rational motion. This allows to keep the degree lower and saves links and joints. If the curve is of degree $d$ and circularity $c$, the bounds for links and joints are $3d-4c+2$ and $\frac{9}{2}d-6c+1$, respectively.

Another advantage of our spatial approach concerns a certain defect in Kempe’s original construction that later was even considered a flaw [@demaine07 Section 3.2]. Kempe used parallelogram and anti-parallelogram linkages as basic building blocks of his linkages. It is well known that the configuration curves of these linkages consists of two irreducible algebraic components that intersect at flat folded positions. That is, the linkage may switch between parallelogram and anti-parallelogram mode, thus entering unwanted components of the configuration curve. The effect is that Kempe’s linkages draw more than the originally intended curve. At the cost of introducing additional links and joints, this defect can be overcome by the “bracing constructions” of [@kapovich02; @demaine07]. The approach of [@gallet15] uses anti-parallelograms and is therefore subject to the same defect and its resolution.

The basic building blocks of our approach are Bennett linkages whose configuration curve has only one irreducible component. Thus, no additional links and joints are needed to prevent the linkage from switching modes. We also capture this in the phrase “the configuration curve is free of spurious components”.

This article uses several results from other, recently published, papers. Whenever we use such a result we give a concise summary and references. Moreover, we provide algorithmic descriptions so that a reader of this paper will be able to construct linkages for drawing an arbitrary rational space curve. We continue this article with a formulation of the main theorem and an overview of its proof in . In we provide a concise introduction to dual quaternions and motion polynomials. The proof of our main theorem is done in . It is subdivided into several steps: Construction of a minimal motion to the given rational curve, factorization of this motion, and subsequent linkage construction by means of “Bennett flips”. In we present several examples to illustrate important points of our construction. In the concluding we discuss our result and ideas. We mentioned implementation issues and outline possible extension and application.

Main theorem and overview of proof  {#sec:overview}
===================================

Our main result in this paper is a statement about linkages and bounded rational curves in three-space. A rational curve is a curve admitting a parametric equation of the shape $X = x_0^{-1}(x_1,x_2,x_3)$ with polynomials $x_0,x_1,x_2,x_3 \in {\mathbb{R}}[t]$ and $x_0 \neq 0$. It is no restriction to assume that this parametric equation is *reduced,* that is, $\gcd(x_0,x_1,x_2,x_3) = 1$ because we may always divide by a common factor. The *degree* of the rational curve is the maximum of the polynomials $x_0$, $x_1$, $x_2$, and $x_3$ in reduced form. The *circularity* of a reduced rational parametric equation is $c \coloneqq \frac{1}{2}\deg\gcd(x_0,x_1^2+x_2^2+x_3^2)$. It counts the number of intersection points with the absolute conic of Euclidean geometry, is a positive integer and invariant with respect to rational re-parameterizations and similarity transformations. Finally, the rational curve is called *bounded,* if $x_0$ has no real zeros and $\deg(x_0)\ge\deg(x_1),\deg(x_2),\deg(x_3)$. Note that in this sense bounded segments of unbounded rational curves are bounded rational curves.

A linkage in our context consists of a set of lines in space, called the *joints*, and links (rigid bodies which could have different shapes) that connect two or more axes. Whenever two links are connected by a joint, their relative position is constrained to a rotation about their common joint. More precisely, the relative position is determined by the rotation angle about this joint with respect to a given reference configuration. The set of all tuples of possible rotation angles is called the linkage’s *configuration space.* If it is of dimension one, we call it a *configuration curve* and say the linkage has *one degree of freedom.* If this is the case, we designate one link as fixed and another as moving. We view the relative displacements of the moving link with respect to the fixed link as a curve in ${\mathrm{SE}(3)}$. The *orbit* or *trajectory* of a point attached to the moving link is the locus of all positions in space when the point is subject to all possible displacements in this curve. A linkage is called *spherical,* if all axes are concurrent and *planar* if they are parallel. The trajectories of spherical linkages are spherical curves and the trajectories of planar linkage are curves in parallel planes. For a more formal definition of (at least planar) linkages we refer to [@gallet15].

Let us illustrate some of these concept at hand of a Bennett linkage [@bennett03; @bennett14; @baker98; @perez04] which will play a crucial role in our linkage construction in . A Bennett linkage is a spatial four-bar linkage with one degree of freedom. Its four axes $\ell_1$, $\ell_2$, $\ell_3$, $\ell_4$ are the perpendiculars to two incoming edges in the vertices of a spatial parallelogram, that is, a spatial quadrilateral with equal opposite edge lengths. displays an abstract representation and a 3D model of a Bennett linkage. The joint axes $\ell_1$ and $\ell_4$ are attached to the fixed link while $\ell_2$ and $\ell_3$ belong to the moving link. Two things about Bennett linkages are important to us:

-   Bennett linkage constitute the only type of spatial four-bar linkages with one degree of freedom and

-   their configuration curve consists of only one component.

[img/bennett]{} (14,45)[$\ell_1$]{} (16,19)[$\ell_2$]{} (38,3)[$\ell_3$]{} (49,36)[$\ell_4$]{} (58,45)[$\ell_1$]{} (61,19)[$\ell_2$]{} (85,3)[$\ell_3$]{} (94,36)[$\ell_4$]{}

Here is our main result:

\[th:1\] For every bounded rational curve of degree $d$ and circularity $c$ in three space, there exists a spatial revolute linkage with one degree of freedom with at most $3d-4c+2$ links and $\frac{9}{2}d-6c+1$ joints such that the trajectory of one point attached to the moving link is precisely the given rational curve.

Before we embark on a proof of this theorem (which will consume large parts of this paper), we would like to make a few remarks:

-   The theorem talks about *bounded* rational curves. This is necessary because all trajectories of a linkage with only revolute joints are bounded. It is, however, admissible that the rational curve parameterizes a bounded portion of an unbounded curve, for example a line segment.

-   Boundedness also implies that $d$ is even and $c$ is an integer so that our bounds on the number of links and joints are integers as well.

-   The linkage of is not unique. In fact, uncountably many linkages exist. Even planar or spherical curves may be drawn by spatial linkages.

-   However, our approach is capable of producing planar linkages for planar curves () and retains the bounds of [@gallet15] for the numbers of links and joints of bounded planar rational curves.

-   Our approach can also produce spherical linkages for spherical curves. For them, the number of links and joints reduces to $d+2$ and $\frac{3}{2}d+1$, respectively ().

-   The linkages can be constructed in such a way, that their configuration curve is free of spurious components. This is however not the case if the linkage is required to be planar or spherical.

Our proof of is constructive and can be translated into algorithms, mostly based on polynomial algebra over the dual quaternions. Our presentation pays attention to these algorithmic approach and gives ample information for actual implementation. The proof consists of several steps. We begin by constructing a rational motion such that one point has the given rational curve as trajectory. In order to keep small the number of links and joints, it is advantageous to require a minimal motion degree in the dual quaternion model of rigid body displacements. In [@li15a], we proved that these properties determine a unique rational motion which may be computed in rather straightforward manner by .

This rational motion is parameterized by a certain polynomial with dual quaternion coefficients which we call a “motion polynomial”. General motion polynomials can be written, in several ways, as products of linear motion polynomials [@hegedus13]. These factorizations correspond to the decomposition of the rational motion into products of rotations. The axes are determined by the linear motion polynomials and the rotation angles are linked by a common parameter. On these open chains of revolute joints we base our linkage construction. Unfortunately, there are motion polynomials that do not allow factorizations. Even worse, the motion polynomials of minimal degree with prescribed trajectory typically fall into this category. Therefore, we have to artificially raise their degree in such a way that factorizations exist. This can be done by multiplying them with real polynomials as in [@gallet15; @li15b]. This does not change the underlying motion and may be advantageous in certain applied situations. However, the bounds in are only obtained by a refinement of this procedure. We right-multiplying the motion polynomial with a certain quaternion polynomial. This changes the motion but not the trajectory in question. A curious side-effect of this approach is that it may turn a planar or spherical motion into a spatial motion.

Having constructed a factorizable motion polynomial to the prescribed trajectory, we have to construct a linkage. In general, it is possible to combine the open chains obtained from different factorizations to form a linkage with one degree of freedom [@hegedus13; @li13a; @li14ck; @li14ark]. We do, however, not pursue this approach because it seems difficult to prove that the resulting linkage has *always* (not just in general) only a single degree of freedom. Moreover, spurious motion components do exist [@li13a; @li14ck]. Instead, we adapt the scissor-linkage construction of [@gallet15] to the spatial case, replacing the anti-parallelograms of planar linkages by spatial Bennett linkages. This automatically guarantees that the configuration space is of dimension one and has no spurious components.

It should also be mentioned that all algorithms presented here require exact (zero error) computation, which means symbolic methods. These are not possible for ${\mathbb{R}}$, but only for suitable real closed subfields, in particular for the set of real algebraic numbers. Real closure is necessary because we will need to factor a univariate polynomial into its irreducible linear and quadratic factors. In the examples, we try to remain in subfields for which arithmetic does not get too complicated, such as ${\mathbb{Q}}$ or real quadratic extensions.

Dual quaternions and kinematics {#sec:preliminaries}
===============================

This section provides an introduction to dual quaternions and their relation to space kinematics. In particular, we introduce a homomorphism between a certain subgroup of dual quaternions into ${\mathrm{SE}(3)}$ and the important concept of motion polynomials.

Denote by ${\mathbb{H}}$ the non-commutative ring of quaternions. An element $h \in {\mathbb{H}}$ can be written as $h = h_0 + h_1{\mathbf{i}}+ h_2{\mathbf{j}}+ h_3{\mathbf{k}}$. The quaternion units ${\mathbf{i}}$, ${\mathbf{j}}$, and ${\mathbf{k}}$ satisfy the multiplication rules $${\mathbf{i}}^2 = {\mathbf{j}}^2 = {\mathbf{k}}^2 = {\mathbf{i}}{\mathbf{j}}{\mathbf{k}}= -1.$$ By ${\mathbb{D}}$ we denote the ring ${\mathbb{R}}[{\varepsilon}]/\langle {\varepsilon}^2 \rangle$. Its elements are called *dual numbers.* The scalar extension ${{\mathbb{D}}{\mathbb{H}}}\coloneqq {\mathbb{D}}\otimes_{\mathbb{R}}{\mathbb{H}}$ of ${\mathbb{H}}$ by ${\mathbb{D}}$ gives the ring of dual quaternions.

A dual quaternion $h$ may be written as $h = p + {\varepsilon}q$ with quaternions $p$ and $q$, the *primal* and *dual part* of $h$, respectively. The conjugate dual quaternion is ${\overline{h}} = {\overline{p}} + {\varepsilon}{\overline{q}}$ and quaternions in ${\mathbb{H}}$ are conjugated by multiplying the coefficients of ${\mathbf{i}}$, ${\mathbf{j}}$, and ${\mathbf{k}}$ with $-1$. The dual quaternions with non-zero primal part are invertible. The inverse of $h$ is $h^{-1} = {N(h)}^{-1}{\overline{h}}$. Here, ${N(h)} \coloneqq h{\overline{h}} = p{\overline{p}} + {\varepsilon}(p{\overline{q}} + q{\overline{p}})$ denotes the *dual quaternion norm.* It is a dual number and, provided $a \neq 0$, the inverse of number $a + {\varepsilon}b \in {\mathbb{D}}$ is $a^{-1} - {\varepsilon}ba^{-2}$.

Denote by ${\mathbb{S}}$ the multiplicative subgroup of dual quaternions with real, nonzero norm. It acts on ${\mathbb{R}}^3 = \langle {\mathbf{i}}, {\mathbf{j}}, {\mathbf{k}}\rangle$ according to $$\label{eq:1}
  z \mapsto \frac{pz{\overline{p}}+p{\overline{q}}-q{\overline{p}}}{{N(p)}}.$$ This equation defines a homomorphism from ${\mathbb{S}}$ to ${\mathrm{SE}(3)}$. It is surjective and the kernel is the real multiplicative group ${\mathbb{R}}^\star$. Hence, there exists an isomorphism between ${\mathbb{S}}/{\mathbb{R}}^\star$ and ${\mathrm{SE}(3)}$. This is actually Study’s well-known kinematic mapping (or its inverse). Factorizing by ${\mathbb{R}}^\star$ turns ${{\mathbb{D}}{\mathbb{H}}}$ into real projective space ${\mathbb{P}}^7$ and ${\mathbb{S}}$ becomes the Study quadric ${S}\subset {\mathbb{P}}^7$ minus the exceptional three-space of classes of dual quaternions with vanishing primal part. More details can be found for example in [@husty09:_algebraic_geometry_kinematics].

Now we make this group homomorphism parametric. Denote by ${{\mathbb{D}}{\mathbb{H}}}[t]$ the skew ring of polynomials over ${{\mathbb{D}}{\mathbb{H}}}$ with indeterminate $t$. We define multiplication in this ring by the convention that $t$ commutes with all coefficients. This is a natural convention because $t$ will later act as a real motion parameter and ${\mathbb{R}}$ is in the center of ${{\mathbb{D}}{\mathbb{H}}}$. Some notions that have already been defined for ${{\mathbb{D}}{\mathbb{H}}}$ can be transferred to ${{\mathbb{D}}{\mathbb{H}}}[t]$. For $C \in {{\mathbb{D}}{\mathbb{H}}}[t]$ the *conjugate polynomial* ${\overline{C}}$ is obtained by conjugating all coefficients of $C$. If $C = P + {\varepsilon}Q$ with $P, Q \in {\mathbb{H}}[t]$, then $P$ and $Q$ are called *primal* and *dual part,* respectively. The norm polynomial is ${N(C)} \coloneqq C{\overline{C}} = P{\overline{P}} + {\varepsilon}(P{\overline{Q}} + Q{\overline{P}})$. Its coefficients are dual numbers. If $C = \sum_{i=0}^n c_it^i$, the value of $C$ at $h \in {{\mathbb{D}}{\mathbb{H}}}$ is defined as $C(h) \coloneqq \sum_{i=0}^n c_ih^i$. With these definitions, evaluation of polynomials at a fixed value $h \in {{\mathbb{D}}{\mathbb{H}}}$ is not a ring homomorphism. Still, the dual quaternion zeros of polynomials over ${{\mathbb{D}}{\mathbb{H}}}$ have a meaning in our algorithms.

The polynomial $C \in {{\mathbb{D}}{\mathbb{H}}}[t]$ is called a *motion polynomial,* if $C{\overline{C}} \in {\mathbb{R}}[t] \setminus \{0\}$ and if its leading coefficient $\operatorname{{lcoeff}}(C)$ is invertible.

Motion polynomials are a central concept in this article. Their introduction is motivated by the fact that for every $t_0 \in {\mathbb{R}}$, the value $C(t_0)$ is an element of ${\mathbb{S}}$ so that $C$ acts on ${\mathbb{R}}^3$. Varying $t_0$, we get a one-parametric set of rigid body displacements, that is, a motion. By virtue of , the orbit of any point is (part of) a rational curve, whence the motion itself is called *rational.* It is possible to extend the parameter range from ${\mathbb{R}}$ to ${\mathbb{R}}\cup \{\infty\}$: with the definition $C(\infty) \coloneqq \operatorname{{lcoeff}}(C)$, the parametrization of the orbit is continuous except in the points $t_1$ such that $C(t_1)$ has norm zero. One could also represent the map as a regular map from the real projective line to real projective space ${\mathbb{P}}^7$, but this would require a second homogeneous variable for the parameter $t$, which complicates the algebraic theory; hence, we prefer to use an affine parameter space and a projective image.

Of particular importance to us are linear motion polynomials. The linear polynomial $C = t - h$ is a motion polynomial if $C{\overline{C}} = t^2 - (h + {\overline{h}})t + h{\overline{h}}$ is real. This is the case if both $h + {\overline{h}}$ and $h{\overline{h}}$ are real. It is well-known that the motion parameterized by $C$ is either a rotation about a fixed axis or, if the primal part of $h$ is real, a translation in fixed direction. In either case, the parameter value $t = \infty$ corresponds to the identity transformation, that is, zero rotation angle or translation distance.

In this article, we often assume that a given motion polynomial has no nontrivial real factor. We call those motion polynomials *reduced.* From a kinematic viewpoint, this is no restriction as $C$ and $CR$ with $R \in {\mathbb{R}}[t] \setminus \{0\}$ parameterize the same motion. Note, however, that multiplication with a real polynomial is a useful technique to ensure existence of a factorization (see [@gallet15; @li15b] and ).

Proof of main theorem, linkage construction {#sec:construction}
===========================================

In this section we prove . For each step in our constructive proof we provide a theoretical justification, often with references to existing literature, and an algorithmic description. Given is a bounded rational curve by a reduced rational parametric equation $X = x_0^{-1}(x_1,x_2,x_3)$. We also encode it as polynomial $x = x_0 + x_1{\mathbf{i}}+x_2{\mathbf{j}}+ x_3{\mathbf{k}}\in {\mathbb{H}}[t]$. The parametric equation $X$ and the polynomial $x$ are of the same degree $d$.

Motion of minimal degree to given trajectory {#sec:minimal-degree}
--------------------------------------------

The first step is the construction of a rational motion such that the trajectory of one point equals the parametric curve $X$. An obvious and simple choice is the translation along $X$, given by the motion polynomial $C = x_0 - \frac{1}{2}{\varepsilon}(x_1{\mathbf{i}}+x_2{\mathbf{j}}+ x_3{\mathbf{k}})$. However, in order to keep low the number of links and joints, we try to find a motion polynomial $C$ of minimal degree with trajectory $X$. The main result in this context states uniqueness of this motion and characterizes curves for which the trivial translation along the curve is not optimal [@li15a]. In order to fully appreciate it, we need a definition:

\[def:trajectory-degree\] The *trajectory degree* of a reduced rational motion $C = P + {\varepsilon}Q \in {{\mathbb{D}}{\mathbb{H}}}[t]$ is the maximal degree of its trajectories. The *quaternion degree* is the degree of $C$ as polynomial in ${{\mathbb{D}}{\mathbb{H}}}[t]$. The *spherical degree defect* of $C$ is the degree of the real polynomial factor of maximal degree of the primal part $P$.

Some authors refer to the trajectory degree of a reduced rational motion as just the “degree”. However, we have to distinguish between this trajectory degree and the degree of $C$ as polynomial in ${{\mathbb{D}}{\mathbb{H}}}[t]$. The latter was called the motion’s “quaternion degree” in [@juettler93] and we follow this convention. The spherical degree defect accounts for a difference in the respective trajectory degrees of $C$ and its spherical motion component $P$. If the motion polynomial is monic (or at least its leading coefficient is invertible), the spherical degree defect can be computed as degree of $\operatorname{{mrpf}}P \coloneqq \gcd(P,{\overline{P}})$ where $\gcd$ denotes the monic real polynomial factor of maximal degree.

\[th:2\] The rational motion of minimal quaternion degree with a prescribed rational trajectory is *unique.* If the trajectory is of degree $d$ and circularity $c$, this minimal motion is of degree $d-c$ and has a spherical degree defect of $s = d - 2c$.

Lets call the motion of the trajectory’s *minimal motion.* tells us that in general (if the trajectory is of circularity zero), the translation along the trajectory is minimal. But for curves with positive circularity, we can do better. This has effects on our linkage construction: Curves of high circularity lead to minimal motions of low degree and low spherical degree defect and lend themselves well to a realization by a linkage with few links and joints.

The constructive proof of in [@li15a] can be turned into a short algorithm to actually compute minimal motions. We make a few technical assumptions:

-   The reduced rational curve $x = x_0+x_1{\mathbf{i}}+ x_2{\mathbf{j}}+ x_3{\mathbf{k}}$ satisfies $x(\infty) \coloneqq \lim_{t \to \infty} t^{-d}x = 1$. This can always be accomplished by a suitable translation of the coordinate frame.

-   We want to find a motion polynomial $C = P + {\varepsilon}Q$ of minimal degree $d - c$ such that $P{\overline{P}} + 2P{\overline{Q}} = x$. In view of this means that $x$ is the trajectory of the affine origin in ${\mathbb{R}}^3$.

-   We assume that $C$ is monic which is consistent with the assumption $x(\infty) = 1$ and entails that $C(\infty)$ is the identity. This can always be accomplished by a suitable rotation of the coordinate frame about its origin.

An important ingredient in the computation of minimal motions is right division of quaternion polynomials. Given $F$, $G \in {\mathbb{H}}[t]$, there exist unique polynomials $Q, R \in {\mathbb{H}}[t]$, called right quotient and right remainder, with $F = GQ + R$ and $\deg R < \deg G$. In case of monic $G$, they can be computed by . We denote the right quotient by $Q = \operatorname{{rquo}}(F, G)$ and the right remainder by $R = \operatorname{{rrem}}(F, G)$. The latter is used in (Euclidean algorithm) for computing the left gcd of two quaternion polynomials $F, G \in {\mathbb{H}}[t]$ in case of monic $G$. The left gcd is the unique monic polynomial $L = \operatorname{{lgcd}}(F,G)$ of maximal degree such that there exist polynomials $Q, R \in {\mathbb{H}}[t]$ with $F = LQ$ and $G = LR$. The function $\operatorname{{lcoeff}}$ in Line \[line:lcoeff\] of returns the leading coefficient of a polynomial so that $\operatorname{{lcoeff}}(R)^{-1}R$ is monic.

Two polynomials $F, G \in {\mathbb{H}}[t]$, $G$ is monic. Polynomials $Q, R \in {\mathbb{H}}[t]$ such that $\deg R < \deg G$ and $F = GQ + R$. $Q \leftarrow 0$, $R \leftarrow F$ $m \leftarrow \deg F$, $n \leftarrow \deg G$ $c \leftarrow \operatorname{{lcoeff}}(R)$ leading coefficient of $R$ $Q \leftarrow Q + ct^{m-n}$ \[line:Gct\]$R \leftarrow R - Gct^{m-n}$ $m \leftarrow \deg R$ $Q, R$

Two polynomials $F$, $G \in {\mathbb{H}}[t]$, $G$ is monic. Monic polynomial $L \in {\mathbb{H}}[t]$ such that there exist polynomial $Q, R \in {\mathbb{H}}[t]$ with $F = LQ$ and $G = LR$. $R \leftarrow \operatorname{{rrem}}(F, G)$ $G$ \[line:lcoeff\]$\operatorname{{lgcd}}(G, R \operatorname{{lcoeff}}(R)^{-1})$

The computation of the minimal degree rational motion with the prescribed trajectory $x$ is illustrated in . It computes a monic rational motion polynomial $C$ such that the trajectory of the affine origin is parameterized by $x$. The correctness of has been proved in [@li15a]. The function $\operatorname{{quo}}$ in Line \[line:quo\] denotes the quotient of polynomial division for real polynomials. It may also be computed by .

Reduced rational parametric equation $x = x_0 + x_1{\mathbf{i}}+ x_2{\mathbf{j}}+ x_3{\mathbf{k}}$ with $x(\infty) = 1$. Monic motion polynomial $C$ of minimal degree such that $x = P{\overline{P}} + 2P{\overline{Q}}$ (trajectory of affine origin is parameterized by $x$). $g \leftarrow \gcd(x_0, x_1^2+x_2^2+x_3^2)$ \[line:quo\]$w \leftarrow \operatorname{{quo}}(x_0,g)$ quotient of polynomial division in ${\mathbb{R}}[t]$ $D \leftarrow x_1{\mathbf{i}}+ x_2{\mathbf{j}}+ x_3{\mathbf{k}}$ $P' \leftarrow \operatorname{{lgcd}}(D,g)$, $Q' \leftarrow \operatorname{{rquo}}(D,P')$, $C = wP' + \frac{1}{2} {\varepsilon}{\overline{Q'}}$

\[lem:1\] Let $C=P+{\varepsilon}Q$ be a minimal motion to the reduced rational curve $x = x_0 + x_1{\mathbf{i}}+ x_2{\mathbf{j}}+ x_3{\mathbf{k}}$. Then $\operatorname{{mrpf}}(P)$ and $Q{\overline{Q}}$ are relatively prime.

Assume that the trajectory of the origin is $x_0+x_1{\mathbf{i}}+x_2{\mathbf{j}}+x_3{\mathbf{k}}$. Following Algorithm \[alg:minmot\], we define $g \coloneqq \gcd(x_0,x_1^2+x_2^2+x_3^2)$ and $D \coloneqq x_1{\mathbf{i}}+ x_2{\mathbf{j}}+ x_3{\mathbf{k}}$. Then $$P = wP' = \frac{x_0}{g}\operatorname{{lgcd}}(D, g).$$ Because $x$ is reduced, $\gcd(x_1{\mathbf{i}}+ x_2{\mathbf{j}}+ x_3{\mathbf{k}},g) = 1$ and $\operatorname{{mrpf}}(P)=x_0/g$. Moreover, Lemma 3 of [@li15a] is applicable (with $C = D$ and $R = g$) and guarantees that $L \coloneqq \operatorname{{lgcd}}(D, g)$ satisfies $L{\overline{L}} = g$. There exists $D' \in {\mathbb{H}}[t]$ such that $D = LD'$. But then $-D = {\overline{D}} = {\overline{D'}}\,{\overline{L}}$ which implies ${\overline{L}} = \operatorname{{rgcd}}(D,g)$ and also ${\overline{Q}} = \frac{1}{2}\operatorname{{lquo}}(D,{\overline{L}}) = \frac{1}{2}D'$. Thus, $$-4Q{\overline{Q}} = D'{\overline{D'}} = D{\overline{D}}(L{\overline{L}})^{-1} = D{\overline{D}}/g$$ and $\operatorname{{mrpf}}(P)=x_0/g$ and $Q{\overline{Q}}=-(x_1^2+x_2^2+x_3^2)/(4g)$ are relatively prime.

If the rational curve is planar or spherical, then the minimal motion is also planar or spherical, respectively. If a planar curve with a non-planar minimal motion existed, we could reflect the motion in the curve’s plane and obtain a contradiction to uniqueness. For spherical curves, this follows from Folgerung 9 and the proof of Satz 6 of [@juettler93].

Let us look at some examples of minimal motions:

\[ex:1\] Consider the parametric curve $x = t^2 + 1 - 2 a{\mathbf{i}}-2 b{\mathbf{j}}t$ with $a, b \in {\mathbb{R}}$. For $a > b > 0$, it is an ellipse and the minimal motion polynomial is $C = t^2 + 1 + {\varepsilon}(a{\mathbf{i}}+ b{\mathbf{j}}t)$. It parameterizes the translation along the ellipse. If $a > b = 0$, the curve degenerates to a straight line segment and the minimal motion is the translation $C = t^2 + 1 + a {\varepsilon}{\mathbf{i}}$ (back and forth along this segment). If $a = b > 0$, the parametric curve is a circle. Its circularity is one and the minimal motion polynomial $C = t - {\mathbf{k}}+ a{\varepsilon}{\mathbf{j}}$ is linear, as predicted by . It parameterizes the rotation around the circle axis.

\[ex:2\] As a second example, consider Viviani’s curve $x = x_0 + x_1{\mathbf{i}}+
  x_2{\mathbf{j}}+ x_3{\mathbf{k}}$, given by $$x_0 = (1+t^2)^2,\quad
    x_1 = -4t^2,\quad
    x_2 = 2t(1-t^2),\quad
    x_3 = 2t(1+t^2).$$ It lies on the sphere of radius $1$ with center $(-1,0,0)$ and our parameterization satisfies $x(\infty) = 1$. The minimal motion is $C = t^2 - ({\mathbf{j}}+ {\mathbf{k}}- {\varepsilon}({\mathbf{j}}- {\mathbf{k}}))t - {\mathbf{i}}$. It is a spherical motion because it fixes the sphere center $(-1,0,0)$. We call it *Viviani motion.*

Factorization of the bounded minimal degree motion {#sec:factorization}
--------------------------------------------------

Having constructed a monic motion polynomial $C$ with a trajectory $x$, we have converted our trajectory generation problem to a motion generation problem: We are looking for a linkage with one degree of freedom such that one link follows the motion parameterized by $C$. (Note that we are only interested in bounded motions, that is, motions with only bounded trajectories.) This we accomplish by decomposing the motion into the product of rotations about certain axes. The rotation angles are linked by the common motion parameter $t$. The basic tool for this is the factorization theory for motion polynomials as introduced in [@hegedus13] and its extension to non-generic bounded motion polynomials in [@li15b].

\[def:factorization\] A bounded motion polynomial $C$ is said to *admit a factorization* if there exist bounded linear motion polynomials $t-h_1$, …, $t-h_n$ such that $$\label{eq:2}
    C = (t-h_1) \cdots (t-h_n).$$

We already said that each linear factor $t - h_i$ in parameterizes a rotation with fixed axes or translation in fixed direction. Because $t - h_i$ is bounded, the later cannot occur here. Hence, the product parameterizes the composition of such rotations. Note that a factorization of the form need not exist and if it exists, it need not be unique.

Call a motion polynomial “generic” if its spherical degree defect () is zero. A generic motion polynomial can always be factored [@hegedus13 Theorem 1] but the factorization is in general not unique. Elliptic and circular translation and the Viviani motion serve as examples:

\[ex:3\] The elliptic translation of does not admit a factorization if $a \neq b$. If $a = b > 0$, it admits infinitely many factorizations $$C = t^2 + 1 + a{\varepsilon}({\mathbf{i}}+ {\mathbf{j}}t)
      = (t - {\mathbf{k}}+ {\varepsilon}(\alpha{\mathbf{i}}+ (\beta+a){\mathbf{j}}))
        (t + {\mathbf{k}}- {\varepsilon}(\alpha{\mathbf{i}}+ \beta{\mathbf{j}}))$$ with $\alpha$, $\beta \in {\mathbb{R}}$. The Viviani motion in admits only the factorization $$\label{eq:3}
    C = t^2 - ({\mathbf{j}}+ {\mathbf{k}}- {\varepsilon}({\mathbf{j}}+ {\mathbf{k}}))t - {\mathbf{i}}= (t - {\mathbf{k}}+ {\varepsilon}{\mathbf{j}})(t - {\mathbf{j}}- {\varepsilon}{\mathbf{k}}).$$ By considering primal parts only (the dual parts are merely there because the sphere center is not the affine origin), we see that it is the composition of rotations with equal angular speed about the second and the third coordinate axis.

An algorithm for computing factorizations of generic motion polynomials has been presented in [@hegedus13]. It is displayed in and . The assumptions on $M$ and $C$ in guarantee that the remainder $R$ in Line 1 has an invertible leading coefficient (compare [@hegedus13 Theorem 3]). They are met in because $C$ is assumed to be generic. The non-uniqueness of the factorization comes from the undetermined order of the quadratic factors in Line \[line:quadfac\] of . In Line \[line:lquo\] we compute the quotient of polynomial left division. This can be done by a variant of but with $R-Gct^{m-n}$ in Line \[line:Gct\] replaced by $R-ct^{m-n}G$.

Monic, bounded motion polynomial $C \in {\mathbb{D}}{\mathbb{H}}[t]$, quadratic factor $M$ of $C{\overline{C}}$ that does not divide the primal part of $C$. Bounded linear motion polynomial $t - h$ such that $C(h) = M(h) = 0$. $R \leftarrow \operatorname{{rrem}}(C,M)$ $R = at + b$ with $a,b \in {\mathbb{D}}{\mathbb{H}}$. \[li:zero\]$h \leftarrow $ unique zero of $R$ $h = -a^{-1}b$ ($a$ is invertible) $h$.

$C = P + {\varepsilon}Q \in {\mathbb{D}}{\mathbb{H}}[t]$, a generic, monic motion polynomial. A list $L=[t-h_1,\ldots,t-h_n]$ of bounded linear motion polynomials such that $C=(t-h_1) \cdots (t-h_n)$. $L \leftarrow [\,]$ initialize empty list \[line:quadfac\]$F \leftarrow [M_1,\ldots,M_n]$ Each $M_i \in {\mathbb{R}}[t]$, $i\in\{1,\ldots,n\}$ is a\
quadratic, irreducible factor of $C{\overline{C}} \in {\mathbb{R}}[t]$. $F \leftarrow {\ensuremath{\text{remove}(F, M_i)}}$. Remove $M_i$ from list $F$. \[line:czero\]$h \leftarrow \operatorname{{czero}}(C, M_i)$ $L \leftarrow {\ensuremath{\text{concat}([t-h], L)}}$ Add $t-h$ to start of list $L$. \[line:lquo\]$C \leftarrow \operatorname{{lquo}}(C,t-h)$ Quotient of left division, variant of . $L$.

\[ex:4\] cannot be used to factor the elliptic or circular translation of Examples \[ex:1\] and \[ex:3\] because its primal part $t^2+1$ is real. It fails in Line \[li:zero\] of where the dual quaternion $a$ is not invertible. We can, however, use to obtain the factorization of the Viviani motion. Because of $C{\overline{C}} = (1+t^2)^2$ the quadratic factors of $C{\overline{C}}$ are all equal ($M_1 = M_2 = 1+t^2$) and the output of is, indeed, unique.

Our linkage construction requires existence of at least one factorization of the motion polynomial $C$. Thus, we have to find a way to “factorize” non-generic motion polynomials as well. One possibility to do this has been presented in [@li15b]. There, we showed that for every bounded motion polynomial $C = P + {\varepsilon}Q$ of degree $n$ a polynomial $R \in {\mathbb{R}}[t]$ of degree $m \le \deg\operatorname{{mrpf}}(P)$ exists such that $CR$ admits a factorization. This statement for planar motion polynomials has already been proved in [@gallet15]. Although not reduced, the motion polynomial $CR$ parameterizes the same motion as $C$. Thus, at the cost of possibly doubling the degree of $C$, we can find a factorized representation to base our linkage construction upon. In fact, the worst case $m = n$ occurs for translational motions, that is, for generic (non-circular) trajectories.

Multiplication with $R \in {\mathbb{R}}[t]$ changes the algebraic properties of the motion polynomial but not the motion itself. However, for our purpose it is sufficient to preserve just one particular trajectory. Therefore, the following refinement is conceivable. If $H \in {\mathbb{H}}[t]$ is a quaternion polynomial, the orbit of the affine origin with respect to $CH$ is the same as the orbit with respect to $C$. Indeed, if $C = P + {\varepsilon}Q$, this orbit is parameterized by $P{\overline{P}} + 2P{\overline{Q}}$ but, because of $H{\overline{H}} \in {\mathbb{R}}[t]$, also by $$PH{\overline{PH}} + 2PH{\overline{QH}} =
  P(H{\overline{H}}){\overline{P}} + 2P(H{\overline{H}}){\overline{Q}} =
  (H{\overline{H}})(P{\overline{P}} + 2P{\overline{Q}}).$$ In order to retain the orbit of a point different from the affine origin, we can similarly right-multiply with a motion polynomial that fixes that point. Besides the extension to three-dimensions, a major contribution in this article over [@gallet15] is to base our linkage construction on factorizations of $CH$ instead of $CR$, thus improving the bounds on the number of links and joints, even in the planar case. But before doing so we have to answer three questions:

-   Given a motion polynomial $C$ of minimal degree to a bounded trajectory, does there always exist a quaternion polynomial $H$ such that $CH$ admits a factorization?

-   Assuming a positive answer to the previous question: How can we determine $H \in {\mathbb{H}}[t]$?

-   Finally, how can we compute the factorization of $CH$. Note that will not do unless it can already be used to factorize $C$ (in which case we simply have $H = 1$).

The first question will be positively answered in , below. Its proof answers the second and third question.

A polynomial $P \in {\mathbb{H}}[t]$ of degree $n$ and without non-trivial real factors can have at most $n$ quaternion zeros. If $P$ has real factors, the situation is slightly more complicated. However, with the boundedness condition, we will only encounter the simpler situation that $\operatorname{{mrpf}}(P)$ is a *strictly positive* real polynomial, i.e., it is irreducible over ${\mathbb{R}}$. Then the quaternion zeros of $\operatorname{{mrpf}}(P)$ are precisely the quaternion zeros of the irreducible, real, quadratic factors of $\operatorname{{mrpf}}(P)$ and these are well known:

\[lem:2\] If the real polynomial $R = t^2 + bt + c$ is irreducible over ${\mathbb{R}}$ ($4c - b^2 > 0$), the set of its quaternion zeros is $$\{\tfrac{1}{2}(-b + s_1{\mathbf{i}}+ s_2{\mathbf{j}}+ s_3{\mathbf{k}}) \mid (s_1,s_2,s_3)\in{\mathbb{R}}^3,\ s_1^2+s_2^2+s_3^2=4c-b^2 \}.$$

One consequence of is the existence of a unique zero whose vector part (the projection onto $\langle {\mathbf{i}}, {\mathbf{j}}, {\mathbf{k}}\rangle$) equals a positive multiple of an arbitrary non-zero vector $v \in {\mathbb{R}}^3$. We call this a zero in *direction of $v$.*

We say that a motion polynomial $C=P+{\varepsilon}Q$ is *tame* if $\operatorname{{mrpf}}(P)$ and $Q{\overline{Q}}$ are relatively prime. Note that minimal motions are always tame by Lemma \[lem:1\]. The following lemma allows to reduce the degree of $\operatorname{{mrpf}}(P)$ for tame polynomials.

\[lem:3\] Consider a tame, monic, and bounded motion polynomial $C = P + {\varepsilon}Q$ and denote by $F \in {\mathbb{R}}[t]$ a monic, quadratic and irreducible factor of $p
  \coloneqq \operatorname{{mrpf}}(P)$. Then there exists a tame, monic, and bounded motion polynomial $C' = P' + {\varepsilon}Q'$ such that $\operatorname{{mrpf}}(P') = \operatorname{{mrpf}}(P)/F$ and linear quaternion polynomials $L$, $L'$ such that $CL = L'C'$.

By Lemma \[lem:2\], we can write $F=L{\overline{L}}$ for some monic linear quaternion polynomial $L = t - h$. If $F$ divides $QL$, then $F^2$ divides $Q{\overline{Q}}L{\overline{L}}=Q{\overline{Q}}F$. But then $F$ would divide $Q{\overline{Q}}$ which contradicts the tameness assumption. So, $F$ does not divide $QL$ and we can use to compute a common zero ${\overline{h'}}$ of ${\overline{QL}}$ and $F$. Moreover, it is no loss of generality to assume that $t-{\overline{h}}$ avoids the finitely many right factors of $P/p$ and $t-h'$ avoids the finitely many left factors of $P/p$. Setting $L' \coloneqq t-h'$ and $Q' \coloneqq \operatorname{{rquo}}(QL, L')$, we obtain $QL = L'Q'$. Then $$CL = PL + {\varepsilon}QL
       = L'{\overline{L'}}(P/F)L + {\varepsilon}L'Q'
       = L'({\overline{L'}}(P/F)L + {\varepsilon}Q'),$$ and we set $C' \coloneqq P' + {\varepsilon}Q'$ where $P' \coloneqq {\overline{L'}}(P/F)L$. By a standard result on quaternion polynomials $\operatorname{{mrpf}}(P')=\operatorname{{mrpf}}(P/F)$, because additional real factors only arise in products $P_1P_2$ when a linear right factor of $P_1$ is conjugate to a linear left factor of $P_2$ ([@li15a Lemma 1] or [@cheng16 Proposition 2.1]). Finally, $C'$ is also tame and bounded, because the norm of the dual part has not changed and the minimal real polynomial factor only got smaller.

\[th:3\] Given a tame monic bounded motion polynomial $C = P + {\varepsilon}Q \in {{\mathbb{D}}{\mathbb{H}}}[t]$ there exists a polynomial $H \in {\mathbb{H}}[t]$ of degree $$\deg H = \tfrac{1}{2}\deg\operatorname{{mrpf}}(P)$$ such that $CH$ admits a factorization.

We proceed by induction on $n \coloneqq \deg\operatorname{{mrpf}}(P)$.

If $n=0$, then $C$ is generic and can be factored by Algorithm \[alg:gfactor\].

Assume that $\deg\operatorname{{mrpf}}(P)>0$ and let $F$ be a monic, irreducible, quadratic factor of $\operatorname{{mrpf}}(P)$. By Lemma \[lem:3\], there exist linear polynomials $L$, $L' \in {\mathbb{H}}[t]$ and a tame motion polynomial $C' = P' + {\varepsilon}Q'$ such that $L'C'=CL$ and $\deg\operatorname{{mrpf}}(P')=n-2$. By induction hypothesis, there exists a quaternion polynomial $H'$ of degree $(n-2)/2$ such that $C'H'$ can be factorized, say $C'H'=M_1 \cdots M_{d}$ for suitable rotation polynomials $M_1$,…,$M_d$. Then we set $H \coloneqq LH'$ and we have a factorization $CH = CLH' = L'C'H' = L'M_1\cdots M_d$.

displays pseudocode, derived from the proofs of and , to compute a factorization for a tame motion polynomial $C$. It returns a list $[L_1,\ldots,L_n]$ of linear motion polynomials and $H \in {\mathbb{H}}[t]$ such that $L_1 \cdots L_n = CH$. The correctness is clear from the proof of .

Tame motion polynomial $C = P + {\varepsilon}Q \in {{\mathbb{D}}{\mathbb{H}}}[t]$. Pair $(M,H)$ consisting of a list $M = [L_1,\dots,L_n]$ of linear motion polynomials and a quaternion polynomial $H$ such that $CH = L_1 \cdots L_n$. $(\operatorname{{gfactor}}(C), 1)$ Choose an irreducible quadratic factor $F$ of $\operatorname{{mrpf}}(P)$. Choose a random zero $h\in{\mathbb{H}}$ of $F$ and set $L \leftarrow t-h$. \[line:tfactor-randzero\] $E \leftarrow {\overline{QL}}$ $h'\leftarrow {\overline{\operatorname{{czero}}(E, F)}}$ $L'\leftarrow t - h'$ $P'\leftarrow {\overline{L'}}\tfrac{P}{F}L$, $Q'\leftarrow \operatorname{{rquo}}({\overline{E}}, L')$ $C' \leftarrow P'+{\varepsilon}Q'$ $M',H'\leftarrow \operatorname{{tfactor}}(C')$ $({\ensuremath{\text{concat}(L', M')}}, LH')$

In Line \[line:tfactor-randzero\] of we are free to pick one among infinitely many quaternion zeros of an irreducible quadratic polynomial. We only have to avoid finitely many “dangourous” zeros of left or right factors of $P/p$, as mentioned in the proof of . This freedom is quite advantageous for applications of our algorithm in order to fulfill engineering needs. In the planar case, one has to pick the suitable one among two conjugate solutions. This is always possible because $P$ is in a sub-algebra isomorphic to ${\mathbb{C}}$. Hence, we need not distinguish between left and right factors and no two linear factors of $P/p$ are conjugate.

\[ex:5\] We continue and illustrate at hand of the elliptic translation $C = t^2 + 1 + {\varepsilon}(b{\mathbf{j}}t + a{\mathbf{i}})$ with $a > b \ge 0$. We have $f = t^2+1$ and may choose $h = {\mathbf{i}}$ and $L = t - {\mathbf{i}}$ in Line \[line:tfactor-randzero\]. With $P = t^2 + 1$ and $Q = b{\mathbf{j}}t + a{\mathbf{i}}$ this yields $$E = {\overline{Q L}} = -b{\mathbf{j}}t^2 - (a{\mathbf{i}}+ b{\mathbf{k}})t + a,\quad
    h' = \frac{(a^2-b^2){\mathbf{i}}+ 2ab{\mathbf{k}}}{a^2+b^2}.$$ The algorithm recursively calls itself with input $C' = P' + {\varepsilon}Q'$ where $$\begin{gathered}
    L' = t - h',\quad
    P' = \frac{{\overline{L'}}PL}{f} = t^2 + \frac{1}{a^2+b^2}\bigl( 2b(a{\mathbf{k}}- b{\mathbf{i}})t + a^2 - 2ab{\mathbf{j}}- b^2 \bigr),\\
    Q' = \operatorname{{rquo}}({\overline{E}}, L') = b{\mathbf{j}}t + \frac{a}{a^2+b^2}\bigl( (a^2-b^2){\mathbf{i}}+ 2ab{\mathbf{k}}\bigr).
  \end{gathered}$$ It admits the factorization $C' = (t-k_1)(t-k_2)$ where $$k_1 = -\frac{(a^2-b^2){\mathbf{i}}+ 2ab{\mathbf{k}}}{a^2+b^2}
          - {\varepsilon}{\mathbf{j}}\frac{a^2+b^2}{2b},
    \quad
    k_2 = {\mathbf{i}}+ {\varepsilon}{\mathbf{j}}\frac{a^2-b^2}{2b}.$$ This gives the factorization $$\label{eq:4}
      CH = (t-h')(t-k_1)(t-k_2).$$ The quaternion polynomial factor equals $H = t - {\mathbf{i}}$.

Note that above factorization is spatial even if the elliptic translation is a planar motion. In order to obtain a planar factorization, we may select $h =
  {\mathbf{k}}$ and $L = t - {\mathbf{k}}$ in Line \[line:tfactor-randzero\]. This choice gives a simple planar factorization: $$E = -b{\mathbf{j}}t^2 - (a-b){\mathbf{i}}t - a {\mathbf{j}},\quad
    L' = t + {\mathbf{k}},\quad
    C' = t^2 - 2{\mathbf{k}}t - 1 + {\varepsilon}(b{\mathbf{j}}t + a{\mathbf{i}})$$ and $$\label{eq:5}
    CH = (t + {\mathbf{k}})(t-{\mathbf{k}}- \tfrac{1}{2}{\varepsilon}{\mathbf{j}}(a - b))(t-{\mathbf{k}}+ \tfrac{1}{2}{\varepsilon}{\mathbf{j}}(a + b))$$ where $H = t - {\mathbf{k}}$.

One can show that all trajectories of the motion $CH$ in are ellipses (or line segments). In the spatial case, the ellipses’ planes are not all parallel. This is a characterizing property of the *Darboux-motion* whose factorizations have already been discussed in [@li15c].

Bennett flips {#sec:bennett-flips}
-------------

In we showed how to factor a bounded motion polynomial, possibly after right multiplication with a quaternion polynomial, into the product of bounded linear motion polynomials. This section is a little intermezzo before constructing linkages from these factorizations in . It introduces a technique we call “Bennett flip”. It will be an essential component of our linkage construction.

In general, a motion polynomial admits several factorizations, each giving rise to an open chain of revolute joints that is capable of performing the motion parameterized by $C$. The distal joints of different factorizations can be attached to a common link and the resulting multi-looped linkage can still perform the motion $C$. Adding sufficiently many factorizations one can reasonably expect to reduce the dimension of the linkages configuration space to one. This idea has already been successfully applied for constructing linkages for engineering applications [@hegedus15:_four_pose_synthesis] but it is not really suitable for proving the general statement of because it may fail to produce linkages with only one degree of freedom. Consider, as a warning, the Viviani motion . It admits only one factorization and hence gives raise to just one single chain with two revolute joints and two degrees of freedom.

It is, however, possible to use the above idea in the special case of quadratic motion polynomials. They are sufficiently simple to allow a complete discussion of all unwanted cases. Once this is available we can combine degree two motion polynomials and their linkages to generate mechanisms that satisfy the criteria of .

\[def:bflip\] The *Bennett flip* is the map $$\operatorname{{bflip}}\colon {{\mathbb{D}}{\mathbb{H}}}^2 \setminus \{ (h_1,h_2) \mid {\overline{h_1}} = h_2\} \to {{\mathbb{D}}{\mathbb{H}}}^2,\quad
      (h_1,h_2) \mapsto (k_1,k_2).$$ where $k_2 \coloneqq -({\overline{h_1}}-h_2)^{-1}(h_1h_2 - h_1{\overline{h_1}})$ and $k_1 \coloneqq h_1 + h_2 - k_2$.

In order to understand the idea behind , take two rotation quaternions $h_1$, $h_2$ with ${\overline{h_1}} \neq h_2$, set $(k_1,k_2) \coloneqq
\operatorname{{bflip}}(h_1,h_2)$ and consider the polynomials $C = (t-h_1)(t-h_2)$, $C{\overline{C}} =
M_1M_2$ where $M_1 = (t-h_1)(t-{\overline{h_1}})$ and $M_2 = (t-h_2)(t-{\overline{h_2}})$. From $$(t-h_1)(t-h_2) = (t-h_1)(t-{\overline{h_1}}) + ({\overline{h_1}}-h_2)t + h_1h_2 - h_1{\overline{h_1}}$$ we see that $k_2$ is the zero of $\operatorname{{rrem}}(C,M_1)$ and $k_1$ is the zero of $\operatorname{{lquo}}(C,t-k_2) = t - k_1$. In other words, $k_1$ and $k_2$ are obtained by applying to $C = (t-h_1)(t-h_2)$ and yield the second factorization $C = (t-k_1)(t-k_2)$. This interpretation accounts for the name “Bennett flip”: Given a rotation quaternion $h$, denote its axes by ${\ell(h)}$. In general the axes ${\ell(h_1)}$, ${\ell(h_2)}$, ${\ell(k_2)}$, and ${\ell(k_1)}$ form a Bennett linkage. Exceptional cases exist and will be described in detail.

\[prop:bflip\] Consider two rotation quaternions $h_1$, $h_2 \in {{\mathbb{D}}{\mathbb{H}}}$ with ${\overline{h_1}} \neq h_2$ and let $(k_1,k_2) \coloneqq
  \operatorname{{bflip}}(h_1,h_2)$. Then the following hold:

1.  Also $k_1$ and $k_2$ are rotation quaternions.

2.  The restriction of the Bennett flip to pairs of rotation quaternions is an involution, that is, $\operatorname{{bflip}}(k_1,k_2) = (h_1,h_2)$.

3.  The restriction of the Bennett flip to pairs of rotation quaternions is birational.

4.  We have $\operatorname{{mp}}(k_1) = \operatorname{{mp}}(h_2)$ and $\operatorname{{mp}}(k_2) =
        \operatorname{{mp}}(h_1)$ where $\operatorname{{mp}}(h) \coloneqq (t-h)(t-{\overline{h}})$ is the *minimal polynomial* of $h \in {{\mathbb{D}}{\mathbb{H}}}$.

5.  We have $\operatorname{{bflip}}(h_2,{\overline{k_2}}) = ({\overline{h_1}},k_1)$, $\operatorname{{bflip}}({\overline{k_2}},{\overline{k_1}}) = ({\overline{h_2}},{\overline{h_1}})$ and $\operatorname{{bflip}}({\overline{k_1}},h_1) = (k_2,{\overline{h_2}})$.

Items 1 and 2 follow from the interpretation of the Bennett flip as application of to $C = (t-h_1)(t-h_2)$. Item 2 implies Item 3. Item 4 follows again from because $\operatorname{{mp}}(h) = M_i$ in Line \[line:czero\] of that algorithm. In order to see the last item, we may multiply the equation $(t-h_1)(t-h_2) = (t-k_1)(t-k_2)$ with $t-{\overline{h_1}}$ from the left and with $t-{\overline{k_2}}$ from the right. With $M_1 \coloneqq (t-h_1)(t-{\overline{h_1}}) = (t-k_2)(t-{\overline{k_2}})$ we obtain $M_1(t-h_2)(t-{\overline{k_2}}) = (t-{\overline{h_1}})(t-k_1)M_1$. Because $M_1$ commutes with the other factors, the first equation of Item 5 follows. The other equations follow by iterating this argument.

The statements of on the restriction of $\operatorname{{bflip}}$ to pairs of rotation quaternions are also true for $\operatorname{{bflip}}$ itself. Here, we only need the weaker formulation that allows a simpler proof.

With $(k_1,k_2) \coloneqq \operatorname{{bflip}}(h_1,h_2)$ we have $(t-h_1)(t-h_2) = (t-k_1)(t-k_2)$. This ensures that the four-bar linkage with axes ${\ell(h_1)}$, ${\ell(h_2)}$, ${\ell(k_2)}$, and ${\ell(k_1)}$ moves with at least one degree of freedom. Moreover, it is elementary to see that it moves with at most one degree of freedom, if these axes are all different. If this is not the case, we have ${\ell(h_1)} = {\ell(k_1)}$ and ${\ell(h_2)} = {\ell(k_2)}$ (this comprises the case where all axes coincide). The following lemma provides a sufficient criterion to exclude this.

\[lem:4\] Given are rotation quaternions $h_1$, $h_2$, $k_1$, $k_2$ with $(k_1,k_2)=\operatorname{{bflip}}(h_1,h_2)$.

-   We have ${\ell(h_1)} = {\ell(h_2)}$ if and only if $h_1 -
        {\overline{h_1}}$ and $h_2 - {\overline{h_2}}$ are linearly dependent. In this case, ${\ell(h_1)} = {\ell(h_2)} = {\ell(k_1)} = {\ell(k_2)}$.

-   Provided ${\ell(h_1)} \neq {\ell(h_2)}$, we have ${\ell(h_1)} = {\ell(k_1)}$ and ${\ell(h_2)} = {\ell(k_2)}$ if and only if $\operatorname{{mp}}(h_1) = \operatorname{{mp}}(h_2)$.

The dual quaternion $h_1 - {\overline{h_1}}$ has zero scalar part. Hence, there exist real numbers $l_1,\ldots,l_6$ such that $h_1 - {\overline{h_1}} = l_1{\mathbf{i}}+ l_2{\mathbf{j}}+ l_3{\mathbf{k}}+ {\varepsilon}(l_4{\mathbf{i}}+ l_5{\mathbf{j}}+
  l_6{\mathbf{k}})$ and the Plücker line coordinates of ${\ell(h_1)}$ are $[l_1,l_2,l_3,-l_4,-l_5,-l_6]$. This implies the first claim.

Now we turn to the second claim. By it is obvious that $\operatorname{{mp}}(h_1) = \operatorname{{mp}}(h_2)$ implies equality of axes. Conversely, we have to show $h_i + {\overline{h_i}} = k_i + {\overline{k_i}}$ and $h_i{\overline{h_i}} = k_i{\overline{k_i}}$ for $i \in \{1,2\}$ under the assumption of ${\ell(h_1)} = {\ell(k_1)}$ and ${\ell(h_2)} = {\ell(k_2)}$. This equality of axes implies linear dependence of their Plücker vectors. Hence, there exist real numbers $a_1$, $a_2$, $b_1$, $b_2$ such that $k_1 = a_1 + b_1h_1$ and $k_2 = a_2 + b_2h_2$. By comparing coefficients on both sides of $(t-h_1)(t-h_2) = (t-k_1)(t-k_2)$ we obtain $$(b_1-1)h_1 + (b_2-1)h_2 + a_1 + a_2 = (b_1b_2-1)h_1h_2 + a_1a_2 = 0.$$ The first equation minus its conjugate is $(b_1-1)(h_1-{\overline{h_1}}) + (b_2-1)(h_2-{\overline{h_2}}) = 0$. Because $h_1-{\overline{h_1}}$ and $h_2-{\overline{h_2}}$ are linearly independent, this implies $b_1 = b_2 = 1$. But then, we are left with $a_1+a_2 = a_1a_2 =0$ and $a_1 = a_2 = 0$ follows. Thus, $h_1 = k_1$ and $h_2 = k_2$. But then .4 implies $\operatorname{{mp}}(h_1) = \operatorname{{mp}}(k_2) = \operatorname{{mp}}(h_2)$.

\[rem:flip-mobility\] Summarizing the result of , we can say that the four-bar linkage with axes ${\ell(h_1)}$, ${\ell(h_2)}$, ${\ell(k_2)}$, and ${\ell(k_1)}$ has exactly one degree of freedom if $h_1 - {\overline{h_1}}$ and $h_2 - {\overline{h_2}}$ are linearly independent and $\operatorname{{mp}}(h_1) \neq \operatorname{{mp}}(h_2)$.

Under the assumptions of the previous remark, a four-bar linkage obtained by a Bennett flip is of one of the following types:

-   A Bennett linkage,

-   a planar anti-parallelogram linkage, or

-   a spherical linkage where the connections of opposite joint pairs are of equal length.

The spatial case is clear since Bennett linkages are the only movable spatial four-bar linkages. In particular, the orthogonal distances and angles of opposite axes pairs are equal. The statement on the planar case has been proved in [@gallet15]. The spherical situation is similar but a distinction between parallelogram and anti-parallelogram linkages is neither possible nor necessary. The reason is that a joint may equally well be realized by a circular arc or its supplementary arc. Equal distance of joint pairs follows from projection of the spatial case on the primal part, that is, by considering only the spherical motion component. At any rate, the configuration curve of planar or spherical linkages consists of two irreducible components and only one of them is relevant to us.

\[rem:circular-flip\] It is worth mentioning that techniques similar to Bennett flips are conceivable. For the circular translation $C = t^2+1+{\varepsilon}{\mathbf{i}}(t-{\mathbf{j}})$ one can find infinitely many different factorizations and two of them may be combined, similar to the Bennett flip, to form a parallelogram linkage. This was used to construct new overconstrained 6R linkages in [@li14ck].

Construction of a scissor linkage {#sec:scissor-linkage}
---------------------------------

Now we come to the actual construction of a linkage – the last step in our proof of . In the preceding sections we have shown how to

1.  compute a motion polynomial $C = P + {\varepsilon}Q$ of minimal degree $d - c$ (where $d$ is the curve’s degree and $c$ is its circularity) such that the trajectory of the affine origin equals the given trajectory and

2.  determine a quaternion polynomial $H \in {\mathbb{H}}[t]$ of degree $$m \coloneqq \frac{1}{2}\deg\operatorname{{mrpf}}(P)$$ such that $CH$ admits the factorization $CH = (t-h_1) \cdots (t-h_n)$ with rotation quaternions $h_1,\ldots,h_n \in {\mathbb{D}}{\mathbb{H}}$ and $n = d - c + m$.

This factorization gives rise to an open chain of revolute axes that can generate the motion parameterized by $CH$ in the following way.

-   For $i \in \{1,\ldots,n\}$, the quaternion $h_i$ describes a rotation about the axis ${\ell(h_i)}$ whose Plücker coordinates $[l_1,\ldots,l_6]$ can be computed from $h_i - {\overline{h_i}} = l_1{\mathbf{i}}+ l_2{\mathbf{j}}+ l_3{\mathbf{k}}- {\varepsilon}(l_4{\mathbf{i}}+ l_5{\mathbf{j}}+
      l_6{\mathbf{k}})$.

-   The lines ${\ell(h_1)},\ldots,{\ell(h_n)}$ determine the configuration of the linkage at parameter time $t = \infty$ (zero rotation angle). The configuration at parameter time $t \neq \infty$ is obtained from this configuration by successively subjecting ${\ell(h_{n-i+1})},\ldots,{\ell(h_n)}$ to the rotation $t-h_{n-i}$ for $i = 1,\ldots,n-1$.

This open revolute chain has $n$ degrees of freedom. It is our aim to constrain its motion in such a way that a link attached to the last joint (with axis ${\ell(h_n)}$) performs a motion that can be parameterized by $CH$. The basic technique for doing this is the Bennett flip of . We can constrain the motion of this chain to the motion parameterized by $CH$ by

1.  picking a “suitable” motion polynomial $t - m_0$ and

2.  recursively defining $$\label{eq:6}
        (m_\ell, k_\ell) \coloneqq \operatorname{{bflip}}(h_\ell, m_{\ell-1}),\quad
        \text{for $\ell = 1,\ldots,n$}.$$

This gives us rotation quaternions $h_1,\ldots,h_n$, $k_1,\ldots,k_n$, and $m_0,\ldots,m_n$ that can be assembled to a linkage whose link graph is depicted in . The vertices of the linkgraph correspond to links and the edges correspond to joints. Two vertices (links) are connected by an edge (joint) if relative motion of the two links is constrained by the corresponding revolute joint. The recursion builds the linkage from the bottom row of edges (labeled $h_1$, …, $h_n$) and the first vertical edge (labeled $m_0$) but it is clear that we may equally well start from any other vertical edge $m_i$, $i \in \{1,\ldots,n\}$.

also shows the joint hypergraph (not a graph because the joint triples $(m_i,h_i,h_{i+1})$ and $(m_i,k_i,k_{i+1})$ belong to the same links for $i \in \{1,\ldots,n-1\}$). The structure of this hypergraph suggests the name “scissor linkage” for the resulting linkage type. The axes of $h_1$ and $m_0$ are attached to the fixed link, while $h_n$ and $m_n$ are attached to the moving link. It performs the motion parameterized by the given motion polynomial. In general, each loop $h_i$, $m_i$, $k_i$, $m_{i-1}$ forms a Bennett linkage. In this case the linkage has just one degree of freedom and its configuration curve has a single component. In other words, it satisfies all requirements of . It is, however, possible, that planar or spherical four-bar linkages occur. This may be desirable, acceptable, or not acceptable, depending on circumstances. In order to prove we must, however, avoid coinciding axes, that is, we have to show that one can pick $m_0$ in such a way that the conditions of are never fulfilled.

![Link graph (top) and joint hypergraph (bottom) of scissor linkage[]{data-label="fig:linkgraph"}](img/linkgraph "fig:")\
![Link graph (top) and joint hypergraph (bottom) of scissor linkage[]{data-label="fig:linkgraph"}](img/jointhypergraph "fig:")

\[lem:5\] Given rotation quaternions $h_1,\ldots,h_n \in {{\mathbb{D}}{\mathbb{H}}}$ there exists a rotation quaternion $m_0$ such that the quaternions $m_1,\ldots,m_n$ and $k_1,\ldots,k_n$ obtained from the recursion are well-defined and the four-bar linkage with axes ${\ell(m_{i-1})}$, ${\ell(h_i)}$, ${\ell(m_i)}$, ${\ell(k_i)}$ has precisely one degree of freedom for any $i \in \{1, \ldots, n\}$.

By , we have to avoid linear dependency of $m_{i-1} - {\overline{m_{i-1}}}$ and $h_i-{\overline{h_i}}$ as well as equality $\operatorname{{mp}}(m_{i-1}) = \operatorname{{mp}}(h_i)$ of minimal polynomials. By we have $\operatorname{{mp}}(m_0) = \ldots =
  \operatorname{{mp}}(m_n)$. Thus, in order to ensure different minimal polynomials, we just have to avoid the set $$\bigcup_{i=1}^n
    \{ m \in {{\mathbb{D}}{\mathbb{H}}}\mid m + {\overline{m}} = h_i + {\overline{h_i}},\ m{\overline{m}} = h_i{\overline{h_i}} \}$$ when picking $m_0$. This is the union of at most $n$ algebraic sets of positive codimension.

In order to avoid linearly dependent vector parts, we recursively define maps $$\beta_0\colon m_0 \mapsto m_0,\quad
    \beta_{i-1}^{-1} \circ \beta_i\colon m_i \mapsto m_{i-1} :\iff \operatorname{{bflip}}(m_{i-1},h_i) = (k_i,m_i)$$ for $i \in \{1,\ldots,n\}$. They are well-defined birational maps by and satisfy $\beta_i(m_i) = m_0$.

The vectors $m_i-{\overline{m_i}}$ and $h_i-{\overline{h_i}}$ are linearly dependent if the projection of $m_i$ onto the vector part is in the span of the projection of $h_i$ onto its vector part. This defines a vector subspace $L_i$ of dimension three that $m_i$ should avoid. This is the case if and only if $m_0$ avoids the union $\bigcup_{i=1}^n \beta_i(L_i)$, that is, another finite union of varieties of positive codimension. This is certainly possible.

This finishes our proof of . We just want to explain how to bound the number of links and joints. The minimal degree motion polynomial with a given rational curve of degree $d$ and circularity $c$ as trajectory is of degree $d - c$ and spherical degree defect $s = d - 2c$ (). By , there exist a polynomial $H \in {\mathbb{H}}[t]$ of degree not larger than $\frac{1}{2}s = \frac{1}{2}d - c$ such that $CH$ admits a factorization. The product $CH$ is of degree $n = d - c + \frac{1}{2}d - c = \frac{3}{2}d - 2c$ and this is the same number $n$ as in . The numbers of links and joints are the numbers of vertices and edges, respectively, in the linkgraph, that is, $2(n+1) = 3d - 4c + 2$ and $3n+1 = \frac{9}{2}d - 6c + 1$, respectively.

We conclude this section with a discussion of planar and spherical four-bar linkages as components of the scissor linkage. The summary is that they can be avoided if wanted but can also be enforced if the given rational curve is planar or spherical.

\[cor:1\] Under the assumptions of we may pick $m_0$ in such a way that none of the quadruples $(m_{i-1}, h_i, m_i, k_i)$ is planar or spherical. In particular, our construction yields linkages such that the configuration space is free of spurious components.

The quadruple will be spherical or planar, respectively, if and only if the axes of $m_{i-1}$ and $h_i$ intersect or are parallel. Similar as in the proof of , this defines subvariaties of positive codimension that $m_{i-1}$ should avoid for $i \in \{2,\ldots,n\}$. Mapping back this subvariaties via the maps $\beta_1,\ldots,\beta_n$ adds finitely many further components of positive codimension to the set that $m_0$ should avoid.

shows that we can avoid planar or spherical quadrilaterals in the scissor linkage if we wish. This ensures that the configuration space of the resulting linkage is free from spurious components. This is an important difference to planar versions of Kempe’s Universality Theorem where “bracing constructions” for anti-parallelograms are necessary in order to suitable constrain the configuration space. Of course, this then yields spatial linkages even for planar or spherical curves/motions which may not always be desirable. The next corollary states that it is also possible to generate planar or spherical linkages if the input data is suitable.

\[cor:2\] If, under all assumptions of , the axes of $h_1,\ldots,h_n$ are incident with the same point or are parallel to the same direction, we may pick $m_0$ in such a way that all axes of $m_1,\ldots,m_n$ and $k_1,\ldots,k_n$ are incident with the this point or parallel to this direction, respectively.

For the planar case, this is [@gallet15 Lemma 6.5]. As to the spherical case, assume, without loss of generality that all dual parts are zero. The proof of shows that we can pick $m_0 \in {\mathbb{H}}$ which then implies $m_1,\ldots,m_n \in {\mathbb{H}}$ and the claim follows.

Finally, we mention two ways to improve our bounds on the number of links and joints. The first is just a hint that will often work for spatial linkages without a formal proof. The second is a substantial improvement of Kempe’s Universality Theorem for rational spherical curves.

If two successive four-bars ${\ell(h_i)}$, ${\ell(m_i)}$, ${\ell(k_i)}$, ${\ell(m_{i-1})}$ and ${\ell(h_{i+1})}$, ${\ell(m_{i+1})}$, ${\ell(k_{i+1})}$, ${\ell(m_i)}$ in a scissor linkage are both Bennett linkages, it is, in general, possible to eliminate their common joint $m_i$ without increasing the mobility. The two Bennett linkages are replaced by a closed-loop linkage with six revolute joints and one degree of freedom. (It is of type “Waldron’s double Bennett hybrid” [@dietmaier95 pp. 63–65].) We refrain from any attempts to formalizing this idea because it is a little tricky to guarantee that neither the number of irreducible components nor dimension of the configuration space increases in non-generic situations.

\[cor:spherical\] A spherical rational curve of degree $d$ appears as trajectory of linkage with at most $d+2$ links and $\frac{3}{2}d+1$ joints.

The statement follows from the bounds of and the observation that spherical rational curves are of maximal circularity $c = \frac{1}{2}d$.

Examples {#sec:examples}
========

In this section we present several examples of linkages with given rational curves. They are meant to illustrate type and properties of the linkages we obtain, the degrees of freedom we have in our construction, and how to use them in the design of linkages. Some of them continue previous examples.

\[ex:pascal\] The limacon of Pascal, parameterized by $x = x_0 + x_1{\mathbf{i}}+ x_2{\mathbf{j}}$ where $$x_0 = (1+t^2)^2,\quad
    x_1 = 2t(a-b-(a+b)t^2),\quad
    x_2 = (4a+2b)t^2+2b,$$ has the minimal motion $$C = (t - {\mathbf{k}}+ \tfrac{1}{2}{\varepsilon}{\mathbf{i}}(a+2b))(t - {\mathbf{k}}+ \tfrac{1}{2}{\varepsilon}{\mathbf{i}}a).$$ Because of $C{\overline{C}} = (1+t^2)^2$, this is the only factorization. We select $m_0 = 2{\mathbf{k}}$ and, using the recursion , obtain $$\begin{gathered}
     3m_1 = 6{\mathbf{k}}- 2{\varepsilon}{\mathbf{i}}(a+2b),\quad
     9m_2 = 18{\mathbf{k}}- 4{\varepsilon}{\mathbf{i}}(2a+b),\\
     6k_1 = 6{\mathbf{k}}+ {\varepsilon}{\mathbf{i}}(a+2b),\quad
    18k_2 = 18{\mathbf{k}}- {\varepsilon}{\mathbf{i}}(5a+16b).
  \end{gathered}$$ The resulting linkage for $a = b = 1$ is depicted in , left and bottom. In this case, the curve is a cardioid. The joints are labeled by their corresponding rotation quaternions. The special geometry allows to realize the links connecting $h_1$, $h_2$, $m_1$ and $k_1$, $k_2$, $m_1$, respectively, by straight line segments. The linkage has two flat positions where all joints are collinear. There, either of the two anti-parallelograms ($h_i$, $m_i$, $k_i$, $m_{i-1}$ for $i \in \{1,2\}$) can switch to parallelogram mode. Thus, the motion has four components and only one of them is relevant for drawing the cardioid. Using $m_0 = 2{\mathbf{k}}+ 2{\varepsilon}{\mathbf{j}}$, we obtain a different, less symmetric, linkage to draw the same curve (, right). Here, the triangles $h_1$, $m_1$, $h_2$ and $k_1$, $m_1$, $k_2$ act as links, that is, they are rigid throughout the motion. The motion of the link attached to $h_2$ and $m_2$ is the same for both linkages.

------------------------------------------------------------------------

![Linkages to draw a cardiod[]{data-label="fig:pascal"}](img/pascal2b)

------------------------------------------------------------------------

![Linkages to draw a cardiod[]{data-label="fig:pascal"}](img/pascal3b)

![Linkages to draw a cardiod[]{data-label="fig:pascal"}](img/pascal2c)

We continue the discussion of Viviani’s curve. However, we will not use but the simpler motion polynomial $C = (t-{\mathbf{k}})(t-{\mathbf{j}})$ which is obtained from by a translation. Based on this minimal motion we construct a linkage. We initialize the construction with $m_0 = \tfrac{1}{2}{\mathbf{j}}$ and, using the recursion , compute $$10m_1 = -3{\mathbf{j}}+ 4{\mathbf{k}},\quad
    26m_2 = 5{\mathbf{j}}- 12{\mathbf{k}},\quad
    5k_1 = 4{\mathbf{j}}+ 3{\mathbf{k}},\quad
    65k_2 = 33{\mathbf{j}}+56{\mathbf{k}}.$$ It is already apparent that this linkage has a flat folded position in the plane spanned by ${\mathbf{j}}$ and ${\mathbf{k}}$. One of its configurations is depicted in , left. We may as well construct a different linkage by starting with $m_0 = \tfrac{1}{2}{\mathbf{i}}$ whence we get $$10m_1 = -3{\mathbf{i}}+ 4{\mathbf{k}},\
    50m_2 = 9{\mathbf{i}}+ 20{\mathbf{j}}- 12{\mathbf{k}},\
    5k_1 = 4{\mathbf{i}}+ 3{\mathbf{k}},\
    25k_2 = -12{\mathbf{i}}+ 15{\mathbf{j}}+ 16{\mathbf{k}}.$$ The corresponding linkage is shown in , right. Here, the joint triples $(h_1, h_2, m_1)$ and $(k_1, k_2, m_1)$ are not collinear. Note that maybe more natural choices like $m_0 = {\mathbf{i}}$ or $m_0 = {\mathbf{j}}$ would violate the condition $\operatorname{{mp}}(m_0) \neq \operatorname{{mp}}(h_1)$.

[img/viviani3b]{} (50,91) (17,92) (59,44) (28,21) (80,24) (40,59) (96,33)

[img/viviani4b]{} (47,86) (76,89) (8,66) (0,55) (90,29) (81,70) (86,9)

In our next example, we return to the elliptic translation of and start with the planar factorization . We assume $a \neq 1$, choose $m_0 = -a{\mathbf{k}}- b{\varepsilon}{\mathbf{j}}$ and compute $$\label{eq:7}
    \begin{gathered}
      (1+a)m_1 = -a(a+1){\mathbf{k}}- b{\varepsilon}{\mathbf{j}}(a - 1),\quad
      (1-a)m_2 = a(a-1){\mathbf{k}}- (a^2-2ab+b){\varepsilon}{\mathbf{j}},\\
      (1-a)^2m_3 = -a(a-1)^2{\mathbf{k}}- (3a^2b-2a^2-b){\varepsilon}{\mathbf{j}},\quad
      (1+a)k_1 = -(a+1){\mathbf{k}}- 2b{\varepsilon}{\mathbf{j}},\\
      2(1-a^2)k_2 = -2(a^2-1){\mathbf{k}}+ (a^3-a^2(b-2)-a(6b-a)+3b){\varepsilon}{\mathbf{j}},\\
      2(1-a)^2k_3 = 2(a-1)^2{\mathbf{k}}+ (a^3+a^2(b-4)+a(8b-1)-5b){\varepsilon}{\mathbf{j}}.
    \end{gathered}$$ The centers of the rotation quaternions in describe the linkage in the configuration at $t = \infty$ and we can verify that all joints lie on the first coordinate axis. The linkage is quite similar to the linkage of but requires eight links and ten joints and it is similar to the example of [@gallet15] which was constructed in a similar manner. The linkage has two flat positions at which any of the three anti-parallelograms $m_{i-1}$, $k_i$, $m_i$, $h_i$ may switch to parallelogram mode. Thus, the configuration curve has six components and only one is relevant for drawing the ellipse.

![Linkage to draw an ellipse[]{data-label="fig:elliptic-translation2"}](img/elliptic-translation2b "fig:") ![Linkage to draw an ellipse[]{data-label="fig:elliptic-translation2"}](img/elliptic-translation2c "fig:")

We may also construct a spatial linkage based on the factorization and the rotation quaternion $m_0 = 1 + {\mathbf{j}}+ {\varepsilon}{\mathbf{k}}$. We refrain from displaying the values of $m_1$, $m_2$, $m_3$, $k_1$, $k_2$, and $k_3$ (which would still be possible, even without specifying $a$ and $b$) and rather discuss the resulting spatial linkage (). It shares the linkgraph with the previous example and can be thought of as a scissor linkage made of Bennett linkages. displays a schematic representation where the four links and joints of one Bennett linkage are displayed in the same color (blue, gray, and red, respectively; note that the joints $m_1$ and $m_2$ belong to two Bennett linkages). The axis triples $(h_1,m_1,h_2)$, $(k_1,m_1,k_2)$, $(h_2,m_2,h_3)$, and $(k_2,m_2,k_3)$ are rigidly connected and one point attached to $h_3$ and $m_3$ draws the ellipse. In contrast to all other examples so far, the configuration curve of this linkage is irreducible. One can show that not only one but all trajectories are ellipses (or line segments) but in non-parallel plane. Thus, the linkage generates a so-called Darboux motion [@li15c]. It is possible to remove $m_1$ or $m_2$ without increasing the dimension of the configuration curve but this may come at the cost of introducing spurious components of the configuration curve.

[img/elliptic-translation-b]{} (5,33) (25,33) (15,34) (1,22) (49,10) (62,17) (79,1) (89,2) (95,10) (93,20)

Finally, we illustrate how to draw a bounded portion of an unbounded rational curve. Using with $b = 0$ is prevented because then the choice $m_0 = -a{\mathbf{k}}- b{\varepsilon}{\mathbf{j}}$ is invalid. But using the curve $x = t^2+1-2{\mathbf{i}}$, the minimal motion $C = t^2 + 1 + {\varepsilon}{\mathbf{i}}$, the factor, $H = t - {\mathbf{k}}$ and the rotation quaternion $m_0 = 2{\mathbf{k}}+ \frac{3}{4}{\varepsilon}{\mathbf{j}}$ produces the linkage shown in .

![Linkage to draw a straight-line segment[]{data-label="fig:straight-line"}](img/straight-line)

Discussion of Results and Future Research {#sec:discussion}
=========================================

In order to carry out the computations for this article, we wrote an experimental implementation in the computer algebra system Maple (version 18). Polynomial arithmetic, in particular the computation of $\gcd$-s, is already available in Maple. Factorization over the real algebraic closure is not available, but we worked around that by figuring out, in each example, which field extension is needed. Maple can do the factorization in a given number field; in most of our examples, especially in all examples occurring in Section \[sec:examples\], we do only examples with all factors defined over ${\mathbb{Q}}$.

For applications in engineering, it would be better to have an algorithm that works with floating point numbers with a fixed precision. Exact $\gcd$-computation is then not possible, but approximate versions of $\gcd$-s do exist, for instance [@qrgcd04]. In order to adapt the algorithms in this paper to the approximate setup, one needs to analyze the consequences of errors carefully. We intend to do this in the future.

It is natural to ask whether our construction allows extensions to other joint types. In principle, one could use prismatic (translation) joints to draw unbounded rational curves. An extension of our algorithms to this case might be possible, but we do not yet really know how (so this is another topic for future research). The main problem is the failure of for certain unbounded polynomials. One such example is $t^2-{\varepsilon}{\mathbf{i}}.$ We could not find a factorization into linear motion polynomials even after multiplication with a quaternion polynomial.

By suitably selecting the dual quaternion $m_0$ in the construction of the scissor linkage () it is possible to create intersecting revolute axes (“spherical joints”) in *some* of the involved four-bar linkages. In case of rational motions of degree two, we may produce a linkage composed of two spherical four-bar linkages that has been called “spherically constrained spatial revolute-revolute chain” in the recent paper [@abdul-sater16]. Our approach via Bennett flips is different from that paper but may be used to improve certain aspects in the design process of the car door guiding linkage that was presented there. This is actually the topic of an ongoing research and demonstrates that ideas we presented in this paper may be of engineering relevance.

Acknowledgments {#sec:acknowledgements .unnumbered}
===============

This work was supported by the Austrian Science Fund (FWF): P 26607 (Algebraic Methods in Kinematics: Motion Factorisation and Bond Theory).

[10]{}

Timothy G. Abbott, *Generalizations of [Kempe’s]{} universality theorem*, Master’s thesis, Massachusetts Institute of Technology, 2008.

Kassim Abdul-Sater, Manuel M. Winkler, F. Irlinger, and Tim C. Lueth, *Three-position synthesis of origami-evolved, spherically constrained spatial revolute-revolute chains*, ASME J. Mechanisms Robotics **8** (2016), no. 1.

Ivan I. Artobolevskii, *Mechanisms for the generation of plane curves*, Pergamon Press, 1964.

J. E. Baker, *On the motion geometry of the [Bennett]{} linkage*, Proceedings of the 8th International Conference on Engineering Computer Graphics and Descriptive Geometry (Austin, Texas, USA), 1998, pp. 433–437.

G. T. Bennett, *A new mechanism*, Engineering **76** (1903), 777–778.

[to3em]{}, *The skew isogramm-mechanism*, Proc. London Math. Soc. **13** (1913–1914), no. 2nd Series, 151–173.

Wilhelm Blaschke and Hans R. Müller, *[Ebene Kinematik]{}*, Oldenbourg, 1956.

Erik D. Demaine and Joseph O’Rourke, *Geometric folding algorithms: Linkages, origami, polyhedra*, Cambridge University Press, 2007.

Peter Dietmaier, *[Einfach übergeschlossene Mechanismen mit Drehgelenken]{}*, Habilitation thesis, Graz University of Technology, 1995.

Matteo Gallet, Christoph Koutschan, Zijia Li, Georg Regensburger, Josef Schicho, and Nelly Villamizar, *Planar linkages following a prescribed motion*, accepted for publication in Math. Comput., 2015.

Xiao-Shan Gao, Chang-Cai Zhu, Shang-Ching Chou, and Jian-Xin Ge, *Automated generation of [Kempe]{} linkages for algebraic curves and surfaces*, Mech. Machine Theory **36** (2001), no. 9, 1019–1033.

Gábor Hegedüs, Josef Schicho, and Hans-Peter Schröcker, *Factorization of rational curves in the [Study]{} quadric and revolute linkages*, Mech. Machine Theory **69** (2013), no. 1, 142–152.

[to3em]{}, *Four-pose synthesis of angle-symmetric [6R]{} linkages*, J. Mechanisms Robotics **7** (2015), no. 4.

Liping Huang and Wasin So, *Quadratic formulas for quaternions*, Appl. Math. Lett. **15** (2002), no. 15, 533–540.

Manfred Husty and Hans-Peter Schröcker, *Algebraic geometry and kinematics*, Nonlinear Computational Geometry (Ioannis Z. Emiris, Frank Sottile, and Thorsten Theobald, eds.), The IMA Volumes in Mathematics and its Applications, vol. 151, Springer, 2009.

Bert Jüttler, *[Über zwangläufige rationale Bewegungsvorgänge]{}*, [Ö]{}sterreich. Akad. Wiss. Math.-Natur. Kl. S.-B. II **202** (1993), no. 1–10, 117–232.

Michael Kapovich and John J. Millson, *Universality theorems for configuration spaces of planar linkages*, Topology **41** (2002), 1051–1107.

Alfred B. Kempe, *On a general method of describing plane curves of the nth degree by linkwork*, Proc. London Math. Soc. (1876), 213–216.

Alexander Kobel, *Automated generation of [K]{}empe linkages for algebraic curves in a dynamic geometry system*, Bachelor’s thesis, University of Saarbr[ü]{}cken, 2008, Available at <https://people.mpi-inf.mpg.de/~akobel/publications/Kobel08-kempe-linkages.pdf>.

Zijia Li, *Sharp linkages*, Advances in Robot Kinematics, Springer, 2014, pp. 131–138.

Zijia Li and Josef Schicho, *Classification of angle-symmetric [6R]{} linkages*, Mechanism and Machine Theory **70** (2013), 372–379.

[to3em]{}, *Three types of parallel [6R]{} linkages*, Computational Kinematics, Springer, 2014, pp. 111–119.

Zijia Li, Josef Schicho, and Hans-Peter Schröcker, *[7R]{} [Darboux]{} linkages by factorization of motion polynomials*, Proceedings of the 14th IFToMM World Congress (Shuo-Hung Chang, ed.), 2015.

[to3em]{}, *Factorization of motion polynomials*, submitted for publication, 2015.

[to3em]{}, *The rational motion of minimal dual quaternion degree with prescribed trajectory*, Comput. Aided Geom. Design **41** (2016), 1–9.

Alba J. Perez, *Analysis and design of [Bennett]{} linkages*, Ph.D. thesis, University of California, Irvine, 2004.

Anupam Saxena, *Kempe’s linkages and the universality theorem*, Resonance **16** (2011), no. 3, 220–237.
