---
abstract: 'For a polygonal linkage, we produce a fast navigation algorithm on its configuration space.  The basic idea is to approximate $M(L)$ by the vertex-edge graph of the cell decomposition of the configuration space discovered by the first author.  The algorithm has three aspects: (1) the number of navigation steps does not exceed 14 (independent on the number of edges), (2) each step is a disguised flex of a quadrilateral from one triangular configuration to another, which can be ranged as well understood type of flexes, and (3) each step can be performed in a mechanical way.' 
address: '\* Institute for Informatics and Automation, St. Petersburg, Russia, Saint-Petersburg State University, St. Petersburg, Russia, e-mail:gaiane-panina@rambler.ru.  $^\dag$ University of Utrecht, Mathematisch Instituut, Utrecht, The Netherlands, e-mail: D.Siersma@uu.nl. ' 
author:
- 'Gaiane Panina\*, Dirk Siersma$^\dag$'
title: Motion planning and control of a planar polygonal linkage
---

Introduction
============

In the paper we work with a polygonal linkage (equivalently, with a flexible polygon), that is, with a collection of rigid bars connected consecutively in a closed chain.  We allow any number of edges and any lengths assignments, (under a necessary assumption of the triangle inequality, which guarantees the closing possibility).  The flexible polygon lives in the plane and admits different shapes, with allowed self-intersections.  Taken together, they form the moduli space of the linkage.  In the paper, we produce a motion planning algorithm (equivalently, a navigation algorithm) which explicitly reconfigures one shape to another via some continuous motion.  In the language of the moduli space this means that we present a path leading from one prescribed configuration to another.  We not only indicate the path, but also present a way of forcing the linkage to follow the path. 

Although the problem looks not much complicated (since the more edges we have, the more freedom degree we have), the navigation is not an easy issue because of the (possible) topological complexity of the moduli space. 

Our reconfiguring algorithm is based on a stratification of the moduli space into a cell complex, introduced in [@Pan].  More precisely, we treat the one-skeleton of the complex as an appropriate approximation of the moduli space.  In other words, we have an embedded graph, and we mostly navigate along the graph.  More precisely, the navigation goes as follows: from a given configuration of the linkage, we first reach an appropriate vertex of the graph, then navigate along the graph until we are close to the target configuration, and next, we pass to the target configuration.  There are three important aspects about the algorithm:

1.   The number of steps (i.e., the number of edges of the connecting path) never exceeds 13.  That is, we have a finite time algorithm with at most 14 steps (rather than $n$ or even $log \ n$ complexity). 

2.   Each of the steps (that is, going along an edge of the graph is a disguised flex of a quadrilateral polygonal linkage, which is both simple and well-understood. 

3.   Each of the steps can be performed in a mechanical way. 

The paper is organized as follows.  Section \[SecPrelim\] gives precise definitions and explains the cell structure on the configuration space.  Besides, we present introductory examples and give a formula for the number of vertices of the graph $\Gamma$. The navigation on the graph is in Section \[SecNavigationOnGraph\].  We show that a vertex-to vertex navigation requires at most 13 steps. 

Our next goal is to control the prescribed motions.  We work under assumption that we have a full control of convex configurations.  There are different approaches how to do this: by using Coulomb potential, as in [@KHPS], by mechanically controlling the angles, or in some other way, not to be discussed in the paper.  However we stress that for navigating over edges of the graph, is suffices to control just quadrilaterals, which is a much easier task, and which is well understood in all respects. 

For a navigation from arbitrary point of the moduli space to a vertex requires one more step: we need to connect the starting point to the graph.  There are two different ways to initiate the algorithm in a mechanical way are described in Section \[SecNavigationOnModuli\]. 

The results presented in this paper arose as a natural continuation of the research on Morse functions on moduli spaces of polygonal linkages started in [@khim2010], [@khipan], [@KHPS].  Several approaches to navigation and control of mechanical linkages have previously been discussed, in particular, in [@hausmann], [@hausmannrodriguez], [@khim2010] and [@KHPS].  It seems worthy of noting that some complications related to non-trivial topology of moduli space prevented complete solution to navigation and control problem and served as a main motivation for our research. 

**Acknowledgments** The authors acknowledge useful discussions with George Khimshiashvili and hospitality of CIRM, Luminy, where this research was completed in framework of “Research in Pairs” program in January of 2014. 

 Moduli spaces of planar polygonal linkages {#SecPrelim}
===========================================

We start by a short review of some results on polygonal linkages and their moduli spaces. 

A *polygonal $n$-linkage* is a sequence of positive numbers $L=(l_1,\dots ,l_n)$. It should be interpreted as a collection of rigid bars of lengths $l_i$ joined consecutively in a chain by revolving joints.  In the literature, it is sometimes called *bar-and-joint mechanism*. 

We assume that $L$ satisfies the triangle inequality. 

*A configuration* of $L$ in the Euclidean plane $ \mathbb{R}^2$ is a sequence of points $R=(p_1,\dots,p_{n}), \ p_i \in \mathbb{R}^2$ with $l_i=|p_i,p_{i+1}|$, and $l_n=|p_n,p_{1}|$.

The set $M(L)$ of all configurations modulo orientation preserving isometries of $\mathbb{R}^2$ is *the moduli space, or the configuration space* of the linkage $L$.

The length vector $L$ is called [*generic*]{}, if there is no subset $J\subset [n]$ such that $$\sum_{i \in J} l_i = \sum_{i\notin J} l_i.$$ (Here and in the sequel, $[n]$ denotes the set $\{1,...,n\}$.)

The hyperplanes $$\sum_{i \in J} l_i = \sum_{i\notin J} l_i,$$ called *walls,* decompose $\mathbb{R}^n$ into a collection of [*chambers*]{}. 

Here is a (far from complete) summary of facts about $M(L)$:

-   If no configuration of $L$ fits a straight line, then $M(L)$ is a smooth $(n-3)$-dimensional manifold.  In this case, the linkage is called *generic* [@KapovichMillson].  Throughout the paper we consider only generic linkages. 

-   The topological type of $M(L)$ depends only on the chamber of $L$ [@KapovichMillson]. 

-   As it was shown in [@Pan], $M(L)$ admits a structure of a regular cell complex.  The combinatorics is very much related (but not identical) to the combinatorics of the permutahedron.  The construction is explained later in this section. 

\[dfn:short\] A set $I\subset [n]$ is called [*long*]{}, if $$|I|=\sum_{i \in I} l_i > \sum_{i\notin I} l_i.$$ Equivalently, for a long set $I$, $$|I|>\frac{|L|}{2}.$$

Otherwise $I$ is called [*short*]{}. 

Note that because the genericity assumption, we never have $|I|=\frac{|L|}{2}.$

-   Homology groups of $M(L)$ are free abelian groups.  For a generic length vector $L$, the rank of the homology group $H_k(M(L))$ equals $a_k+a_{n-3-k}$, where $a_i$ is the number of short sets of cardinality $i+1$ containing the longest edge (see [@faS]). 

We stress that the manifold $M(L)$ (considered either as a topological manifold, or as a cell complex) is uniquely defined by the collection of short subsets of $[n]$.

A partition of the set $\{l_1,\dots ,l_n\}$ is called *admissible* if all the parts are non-empty and short. 

Instead of partitions of $\{l_1,\dots ,l_n\}$ we shall speak of partitions of the set $[n]$, keeping in mind the lengths $l_i$.

Assume that for an $n$-linkage $L$, we have the following: $$\forall \ i=1,2,...,(n-1), \hbox{ the set } \{n,i\} \hbox{ is long.}$$ Loosely speaking, we have “one long edge”.  Such a linkage we call an $n$-bow. 

Its moduli space is a sphere (see [@faS]). 

Now we sketch the cell complex stratification of the moduli space $M(L)$ (see [@Pan])

In the paper we make use of the vertex-edge graph of the cell complex, that is, we take into account only zero- and one-dimensional cells.  We treat is as a (combinatorial) graph, keeping also in mind its embedding in the $M(L)$.

This allows us to view the graph as a discrete approximation of the moduli space. 

A more detailed description of the cell complex {#a-more-detailed-description-of-the-cell-complex .unnumbered}
-----------------------------------------------

Below we sketch in some more details the construction and properties of the cell decomposition of $M(L)$, referring the reader to even more details and all the proofs to [@Pan]. 

Given a configuration $P$ of $L$ **without parallel edges**, there exists a unique convex polygon $Conv(P)$ which we call *the convexification of* $P$ such that

1.   The edges of $P$ are in one-to-one correspondence with the edges of $Conv(P)$ .  The bijection preserves the directions of the vectors. 

2.   The induced orientations of the edges of $Conv(P)$ give the counterclockwise orientation of $Conv(P)$ . 

In other words, the edges of $Conv(P)$ are the edges of $P$ ordered by the slope (see Fig.  \[rearrangment1\]).  Obviously, $Conv(P) \in M(\lambda L)$ for some permutation $\lambda
 \in S_n$. The permutation is defined up to some power of the cyclic permutation $(2,3,4,...,n,1)$. We consider $\lambda$ as a cyclic ordering on the set $[n]$.

![ Labeling of a polygon with no parallel edges[]{data-label="rearrangment1"}](rearrangment1.eps){width="10"}

![ Labeling of a polygon with parallel edges[]{data-label="rearrangment2"}](rearrangment2.eps){width="8"}

Conversely, each convex polygon from $ M(\lambda L)$ is the image of some element of $M(L)$ under the above rearranging map. 

Our construction assigns to $P\in M(L)$ the *label* $\lambda$, considered as a cyclic ordering on the set $[n]$. Or, equivalently, a label of a configuration without parallel edges is a cyclically ordered partition of the set $[n]$ into $n$ singletons. 

If $P$ **has parallel edges**, a permutation which makes $P$ convex is not unique.  Indeed, one can choose any ordering on the set of parallel edges. 

The *label* assigned to $P$ is a cyclically ordered partition of the set $[n]$. Fig.  \[rearrangment2\] gives an example with one two-element set and three one-element sets. 

We stress once again that there is no ordering inside a set, that is, we identify two labels whenever they differ on permutations of the elements inside the parts.  For instance, $$(\{1\} \{3 \} \{4  2 56\})\neq(\{3 \}\{1\}  \{4  2 56\})= ( \{3 \}\{1\}\{ 24 56\}).$$

By the triangle inequality, all labels are admissible partitions. 

Two points from $M(L)$ (that is, two configurations) are said to be *equivalent* if they have one and the same label.  Equivalence classes of $M(L)$ we call the *open cells*.  The closure of an open cell in $M(L)$ is called a *closed cell*.  For a cell $C$, either closed or open, its label $\lambda (C)$ is defined as the label of its interior point. 

\[MainThm\][@Pan] The above described collection of open cells yields a structure of a regular CW-complex $CWM(L)$ on the moduli space $M(L)$. Its complete combinatorial description reads as follows:

1.   $k$-cells of the complex $CWM(L)$ are labeled by cyclically ordered admissible partitions of the set $[n]$ into $k+3$ non-empty parts. 

    In particular, the facets of the complex (that is, the cells of maximal dimension $n-3$) are labeled by cyclic orderings of the set $[n]$.

2.   A closed cell $C$ belongs to the boundary of some other closed cell $C'$ iff the partition $\lambda(C')$ is finer than $\lambda(C)$.

3.   The complex is regular, which means that each $k$-cell is attached to the $(k-1)$-skeleton by an injective mapping.  All closed cells are ball-homeomorphic. 

\[ExTwoVertices\] The vertex labeled by $$(\{1,2,5,6,\},\{3,4\},\{7,8\})$$ and the vertex labeled by $$(\{1,2\},\{3,4,5,6\},\{7,8\})$$ are connected by an edge labeled by $$(\{1,2\},\{5,6\},\{3,4\},\{7,8\}).$$

Let $n=4; \ \ l_1=l_2=l_3=1,\ l_4=1/2.$ The moduli space $M(L)$ is known to be a disjoint union of two circles (see [@faS]).  The cell complex $CWM(L)$ is as depicted in Fig.  \[4gon1\]. 

![ $CWM(L)$ for the 4-gonal linkage $(1,1,1,1/2)$[]{data-label="4gon1"}](4gon1.eps){width="6"}

\[ExHexagon\] Assume that for a $4$-linkage $L$, the sets $\{2,3\}$, $\{4,3\}$, and $\{2,4\}$ are short.  An example of such a length assignement is $$l_4=l_2=l_3=1,\ l_1=2,5.$$

The moduli space $M(L)$ is homeomorphic to a circle.  The cell complex is combinatorially a hexagon, that is, there are six vertices connected by six edges into a circle.  The (cyclic) order of the labels of the six vertices is: $$(\{1\}\{2,3\}\{4\})$$ $$(\{1\}\{2\}\{4,3\})$$ $$(\{1\}\{2,4\}\{3\})$$ $$(\{1\}\{4\}\{2,3\})$$ $$(\{1\}\{4,3\}\{2\})$$ $$(\{1\}\{3\}\{4,2\}).$$

For the equilateral pentagonal linkage $L=(1,1,1,1,1)$, the complex $CWM(L)$ has $30$ vertices, $60$ edges, and $24$ pentagonal $2$-cells.  Each vertex is incident to exactly four edges. 

**We first describe combinatorics of the vertex-edge graph:**

As a particular case of Theorem \[MainThm\], vertices are labeled by cyclically ordered partitions of $[n]$ into three non-empty short sets, and the edges are labeled by cyclically ordered partition of $[n]$ into short non-empty short sets.  Two vertices labeled by $\lambda$ and $\lambda'$ are joined by an edge whenever the label $\lambda$ can be obtained from $\lambda'$ by shifting some amount of entries from one set to another. 

**Now we describe embedding:**

Assume that a linkage $L$ is fixed.  Given a label $\lambda=(I,J,K)$, it labels some point $P$ of the $M(L)$, that is, some configuration of $L$. The polygon $P$ can be constructed via the following algorithm. 

**Retrieving a vertex (viewed as a polygon) by its label**

1.   Take a positively oriented triangle with edgelengths $$\sum_Il_i,\ \sum_Jl_i, \hbox{ and }\sum_Kl_i.$$

2.   Assume that each edge is constituted of (short) edges $l_i$. For instance, we decompose the first edge into segments of lengths $\{l_i\}_{i\in I}.$ Their order does not matter. 

3.   Now take all the edges apart, keeping their directions, and rearrange them according to the ordering $1,2,...,n$. We get a closed polygonal chain $P$, see Figure \[FigVertex\]. 

![ Retrieving a vertex from its label.  Each vertex is a disguised triangle[]{data-label="FigVertex"}](Vertex.eps){width="10"}

Taken together, all labels give all configurations that have exactly 3 directions of the edges.  They form the vertex set of the embedded graph $G(L)$.

Now let us explain the way how the edges are embedded,

**Retrieving an edge by its label**

Given a label $\lambda=(I,J,K, N)$, it labels an embedded edge of $\Gamma(L)$, that is, a one-parametric family of configurations.  They are retrieved as follows. 

1.   Take a positively oriented convex quadrilateral with consecutive edgelengths $$\sum_Il_i,\ \sum_Jl_i\ \sum_Kl_i, \hbox{ and } \sum_Nl_i.$$ The set of such quadrilaterals forms a path in $M(L)$ starting from one triangle to another, see Figure \[FigEdge\]. 

2.   As in Algorithm 1, decompose each edge into (short) edges $l_i$.

3.   Exactly as in algorithm 1, take all the edges apart, keeping their directions, and rearrange them according to the ordering $1,2,...,n$. This gives a one-parametric family of closed polygonal chains. 

![ Retrieving an edge from the label $(\{5\}\{1,3\}\{2\}\{4,6\})$. Each edge is a disguised flex of a convex quadrilateral from one convex triangular configuration to another []{data-label="FigEdge"}](Edge.eps){width="14"}

In other words, each embedded edge of the graph $\Gamma(L)$ corresponds to a flex of some quadrilateral, which connects two triangular configurations.  One can perform such a flex (for instance) by compressing one of the diagonals. 

1.   The number of vertices of $\Gamma(L)$ equals $$\sum_{k=1}^n N_k2^{n-k} -2\cdot3^{n-1}+2^n,$$ where $N_k$ is the number of short k-sets. 

2.   For the $n$-bow, $\Gamma(L)$ has the minimal possible number of vertices among all $n$-linkages.  In this case, it equals $2^{n-1}-2$.

Proof.  Crossing a wall means that exactly one short $k$-set $I$ becomes long, and exaclly one long $(n-k)$-set $\overline{I}$ becomes short, where the number $k$ depends on the wall.  Observe that any proper subset of $\overline{I}$ is short both before and after crossing a wall.  A vertex dies whenever its label contains $I$. A vertex arises whenever its label contains $\overline{I}$. This means that the number of vertices changes by adding $(2^k-2)-(2^{n-k}-2)=2^k-2^{n-k}$.

Therefore, $$|Vert(\Gamma)|=\sum_{k=1}^{n}N_k2^{n-k}+X_n,$$ where $X_n$ depends solely on $n$. Our second observation is that for a bow linkage, labels of the vertices are of type $$(\{\hbox{any non-empty proper set } I\subsetneq [n-1]\}, \{\hbox{ the complement } \overline{I}\}, \{n\}).$$ Therefore, $|Vert(\Gamma(n\hbox{-bow}))|=2^{n-1}-2$. This is a kind of a base of induction. 

From the chamber that corresponds to the bow, we can reach any other camera by crossing walls. 

For the $n$-bow,$$N_k=\left\{
                        \begin{array}{ll}
                          0=C_{n-1}^0-1, & \hbox{if } k=0; \\
                          n=C_{n-1}^1+1, & \hbox{if } k=1; \\
                          0=C_{n-1}^{n-1}-1, & \hbox{if }  k=n-1 \\
                          C_{n-1}^k, & \hbox{ otherwise.} 
                        \end{array}
                      \right.$$

$$2^{n-1}-2=\sum_{k=0}^{n}C_{n-1}^k2^{n-k}+ 2^{n-1}-2^n-2+X_n$$ $$X_n=2^n-2\cdot3^{n-1},$$ which yields the final formula. 

As we see, the number of vertices of the graph $\Gamma$ depends exponentially on $n$. However, the valence of the vertices also depends on $n$ exponentially, so one can expect a small diameter (in the graph-theoretic sense, that is, the maximal length of the shortest path between two vertices), and a fast navigating algorithm. 

A vertex of the graph $\Gamma$ labeled by $(IJK)$ has exactly $$2^{i}+2^{j}+2^{k}-6$$ incident edges, where $i,\ j, $ and $k$ are the numbers of elements in $I,\ J,$ and $K$ respectively. 

 Motion planning on the graph $\Gamma(L)$ {#SecNavigationOnGraph}
=========================================

Here we describe a finite-step algorithm of motion planning (or, equivalently, navigation) from an arbitrary vertex of $\Gamma(L)$ to any arbitrary prescribed vertex. 

A *path* means a graph-theoretical path, that is, a consecutive collection of edges.  Its *length*, or *the number of steps* we mean just the number of edges in the path. 

We start with an example demonstrating that we can navigate in a really fast way. 

\[AlgBow\] **(Navigation for the bow linkage)** For any $n$-bow linkage, any two vertices are connected by a path whose length is at most 3.  The path is explicitly described as follows. 

1.   We start with a vertex labeled by $$(I,J,\{n\}).$$ Assume that the target vertex is labeled by $$(\{1,2,...,k\},\{k+1,k+2,...,n-1\},\{n\}).$$ We also can assume that $|J|>1$. If $1 \in I$, then go to the step 2.  If not, shift the entry $1$ to the set $I$ and go to step 2. 

2.   Shift the subset $I \setminus \{1\}$ to the set $J$. We arrive at the vertex labeled by $$(\{1\},\{2,3,...,n-1\},\{n\}).$$

3.   There remains (at most) one step to the target vertex: shift the subset $\{2,3,...,k\}$ to the set $I$.

One could expect an easy navigation for the bow linkage in advance, since the configuration space is just a sphere.  However, for more complicated topological types, it still suffices 13 steps. 

We first learn how to turn polygons inside out. 

\[alg5\]**(Turning a pentagon inside out)** Assume that a $5$-linkage $L$ satisfies the following conditions:

1.   The set $\{1,2\}$ is long,

2.   The set $\{1,5\}$ is long,

3.   $\forall \ i\neq1, \ j\neq1 ,$ the set $\{i,j\}$ is short. 

Then there exists a 4-steps path which turns the configuration $(\{4,5\}\{1\}\{2,3\})$ inside out.  Here is the path: $$(\{4,5\}\{1\}\{2,3\})$$ $$(\{4,5,3\}\{1\}\{2\})$$ $$(\{4,3\}\{1\}\{2,5\})$$ $$(\{4,3,2\}\{1\}\{5\})$$ $$(\{3,2\}\{1\}\{4,5\})$$

\[AlgINsideOut\] **(Turning a polygon inside out)** Assume that a linkage $L$ is fixed. 

1.   If the configuration space $M(L)$ is connected, then from each vertex $V$  (labeled, say, by $(I,J,K)$) there are at most 6 step to its mirror image $(J,I,K)$.

2.   If the $M(L)$ is disconnected, then the vertex $(I,J,K)$ and its mirror image $(J,I,K)$ lie in different connected components, and no connecting path exists. 

The idea is to imitate a pentagon which satisfies the three conditions of the Algorithm \[alg5\] by freezing some of the entries in (this requires 4 more steps).  Here and in the sequel, “freezing” means putting the entries into one separate set and after that, manipulating with the set as with a single entry. 

Assume that $l_1\geq l_k\geq l_m$ are the longest edges of $L$. It is known from [@KapovichMillson] that $M(L)$ is connected if and only if $$l_k+l_m< \frac{|L|}{2}.$$

Our starting point is a vertex labeled by $(I,J,K)$, where $1 \in J$. We also can assume that the entries are ordered counterclockwise, that is, $$(I,J,K)= (\{r+1,r+2,...,p\}\{p+1,p+2,...,n,1,2,...,q\}\{q+1,q+2,...,r\}).$$ Maintaining the ordering, we shift to the middle set as many entries from the first and the last set sets as is possible.  This means that we first decide what entries do we shift from $I$, and what entries do we shift from $K$. Then we make two shifts, which means two steps. 

Note that the choice is not uniquely defined.  However, any choice is good for us. 

So we can assume that the sets $$\{p,p+1,p+2,...,n,1,2,...,q\} \hbox{ and  }\{p+1,p+2,...,n,1,2,...,q, q+1\} \hbox{ are long. } $$

Observe that the set $\{p,q+1\}$ is short.  Indeed, $l_p+l_{q+1}\leq l_k+l_m < \frac{|L|}{2}.$ Therefore the set $$A=\{q+2,q+3,..,r,r+1,...,p-2,p-1\}$$ is not empty.  Now the algorithm splits depending on the number of entries of $A$ which equals $(p-1)-(q+2)+1=p-q-2$.

1.   Assume that $p-q-2=1$, which means that $A$ is a one-element set.  Then we freeze the set $\{p+1,p+2,...,n,1,2,...,q\}.$ After renumbering $$4:= \{p\}, \ 1:=\{p+1,p+2,...,n,1,2,...,q\},$$$$\ 2:=\{q+1\}, \hbox{ and } 3:=A,$$ we arrive at a quadrilateral from Example \[ExHexagon\] which can be turned inside out in three steps. 

2.   Assume that $p-q-2>1$. We divide the set $A$ into two non-empty subsets and freeze the two subsets.  We also freeze the set $\{p+1,p+2,...,n,1,2,...,q\}.$ That is, for instance, we freeze the following three sets of entries: $$\{r+1,r+2,...,p-1\},\ \{p+1,p+2,...,n,1,2,...,q\}, \  \hbox{ and } \{q+2,...,r\}.$$ After renumbering $$4:=\{r+1,r+2,...,p-1\},\ 5:= \{p\}, \ 1:=\{p+1,p+2,...,n,1,2,...,q\},$$$$\ 2:=\{q+1\}, \hbox{ and } 3:=\{q+2,...,r\},$$ we arrive at a pentagon which satisfies the properties from the Algorithm \[alg5\], and therefore can be turned inside out in four steps. 

\[PropEitherOr\] For any $n$-linkage $L$, and any two vertices $V$ and $V$’ of the graph $\Gamma(L)$, $V$ is connected either to $V'$ or to the mirror image of $V'$ by a path whose length is at most 7.  The path is explicitly described as follows.  Assume that the target vertex $V'$ is labeled by $$(\{1,2,...,k\},\{k+1,k+2,...,m\},\{m+1,m+2,...,n\}).$$ Assume also that $l_1$ is the longest edge. 

1.   In two steps we get from $V$ to a vertex labeled by $$(I,\{1\},J)$$ for some $I$ and $J$. This is always possible:

    1.   Assume that $V$ is labeled by $(A,B,C)$, and $1\in B$. Start shifting the entries from $B\setminus \{1\}$ to the set $C$ as many as possible, that is, stop one step before $C$ gets long.  The order in which we treat the entries does not matter.  We can shift all the entries by one step, that is, first decide what entries are to be shifted, and next, shift them as a one subset. 

    2.   Shift the rest of $B\setminus \{1\}$ to the set $A$. 

2.   If one of the sets $I$ or $J$ contains two consecutive entries, we can freeze them.  We freeze all possible pairs of consecutive entries and renumber the edges (preserving the ordering), which gives us a linkage with a smaller number of edges. 

    In any case we have a vertex labeled either by $$(\{3,5,7,...\}, \{1\},\{2,4,6,8,...\}),$$ or by the symmetric image $$(\{2,4,6,8,...\}, \{1\},\{3,5,7,...\}).$$

3.   Pull $2,3,4,...k$ and $3,5,7,...,k\pm 1$ to the middle set for the largest $k$ which is possible. ( This requires 2 steps more).  Thus we arrive at $$(\{k+1,k+3,...\}, \{1,2,3,4,...,k\},\{k+2,k+4,...\}),$$ or to the symmetric image.  So the first entry that we cannot shift to the middle set is $k+1$.

4.   Shift $k+3,k+5,...$ to the third set.  It is possible because $\{1,2,3,4,...,k,k+1\}$ is long. ( One step more.)  We arrive at $$(\{k+1\}, \{1,2,3,...,k\},\{k+2,k+3,....,n\})=$$$$= (\{k+1\}, \{k,k-1,...,2,1\},\{n,n-1,...,k+2,k+3\}),$$ (or to the symmetric image).  Now we have either clockwise or counterclockwise ordering on the entries. 

5.   There are two steps either to the target, or to the mirror image of the target vertex. 

Combining the two above algorithms, we immediately have the theorem:

1.   For any $n$-linkage $L$ with a connected moduli space, any two vertices $V$ and $V$’ of the graph $\Gamma(L)$ are connected by a path whose length is at most 13. 

2.   For any $n$-linkage $L$ with a disconnected moduli space, and any two vertices $V$ and $V$’ of the graph $\Gamma(L)$ lying in the same connected component, $V$ and $V$’ are connected by a path whose length is at most 7. 

The path is constructed explicitly basing on the above propositions.  That is we have the following algorithm:

**Algorithm A**

1.   Starting with a vertex $V$, follow algorithm from Algorithm \[PropEitherOr\].  It may bring us to the target point, and then we are done. 

2.   If on the first step we get the mirror image of the target point, turn it inside out via Algorithm \[AlgINsideOut\]. 

Below we exemplify the steps of the algorithm for one particular heptagonal configuration. 

Assume we have a heptagonal linkage with edge lengths $$l_1=10, \ l_2=1, \ l_3=9, \ l_4=4, \ l_5=9, \ l_6=2, \  \hbox{ and } l_7= 4.$$

Assume that our starting point is $V_1=(\{3,6\}\{1,4,7\}\{2,5\})$, and that the target vertex is $V'=(\{5,6,7\}\{1, 2\}\{3,4\})$. Then Algorithm A runs as is described below and as is depicted in Figure \[FigHeptagon\]. 

1.   The starting point is the vertex of the graph $$V_1=(\{3,6\}\{1,4,7\}\{2,5\}).$$ According to Algorithm \[PropEitherOr\], we go to the point $$V_2=(\{3,6\}\{1,4\}\{2,5,7\}),$$ which is connected with $V_1$ by an edge labeled by $(\{3,6\}\{1,4\}\{7\}\{2,5\})$. Next come the vertices $$V_3=(\{3,4,6\}\{1\}\{2,5,7\})$$ $$\hbox{  and    } V_4=(\{3,4,6\}\{1,
                                        2\}\{5,7\}).$$ Then comes the vertex $$V_5=(\{3,4\}\{1, 2\}\{5,7,6\})=(\{4,3\}\{2,1\}\{7,6,5\}),$$ which is the mirror image of the target point. 

    Now we start turning the configuration inside out, as is prescribed in Algorithm \[AlgINsideOut\]. 

2.   The next point is $$V_6=(\{3,4\}\{1, 2,7,6\}\{5\}).$$ After freezing the middle set, we get a triangular configuration of a quadrilateral to be turned inside out in three steps: $$V_7=(\{3\}\{1, 2,7,6\}\{5,4\}),$$ $$V_8=(\{5,3\}\{1, 2,7,6\}\{4\}),$$ $$V_9=(\{5\}\{1, 2,7,6\}\{3,4\})=(\{5\}\{6,7,1, 2\}\{3,4\}).$$ One more edge brings us to the target point $$V_{10}=(\{5,6,7\}\{1, 2\}\{3,4\})=V'.$$

![ The first part of Algorithm A applied to a heptagonal configuration []{data-label="FigHeptagon"}](heptagon.eps){width="14"}

 Navigation and control on the moduli space {#SecNavigationOnModuli}
===========================================

Here we describe a finite-step algorithm of navigation from an arbitrary (which is not necessarily a vertex of $\Gamma(L)$) point of the moduli space $M(L)$ to an arbitrary prescribed point. 

We work under assumption that we can somehow control the shape of a convex configuration.  At the same time, we explain how to realize the flex mechanically.  As in the previous section, we assume that $l_1$ is the biggest edgelength. 

 Algorithm B {#algorithm-b .unnumbered}
------------

1.   Given a starting configuration $S$ and a target configuration $T$, we take the $(n-3)$-cells of the complex $CWM(L)$ containing $S$ and $T$. We choose $V_S=(I,\{1\},J),$ and $V_T$ to be some vertices of these two cells.  Starting from now, we keep in mind Algorithm A applied for the vertices $V_S$ and $V_T$.

2.   We navigate from $S$ to $V_S=(I,\{1\},J)$. In particular, this means that we spare one step in comparison with Algorithm \[PropEitherOr\]. 

    We realize both $P$ and the convexification $Conv(P)$ as two bar-and-joint mechanisms.  By construction, there is a natural bijection between edges of the two polygons, and the corresponding edges are parallel.  For each pair of parallel edges (one edge from $P$, and the other one from $Conv(P)$), we plug in a pair of parallelograms as is shown in Figure \[FigParall\]. 

    ![ Connecting parallelograms[]{data-label="FigParall"}](parallelograms.eps){width="8"}

    To prevent turning inside out, we add one extra edge inside each of the parallelograms (here we follow [@KM]). 

    Each (convex) flex of $Conv(P)$ uniquely induces a flex of $P$ in such a way that the first polygon remains the convexification of the second one.  Therefore, the task is to bring the convex polygon $Conv(P)$ to a triangular configuration.  By assumption, we can control $Conv(P)$, and therefore, we have a controlled way of bringing $P$ to the vertex $(I,\{1\},J).$

3.   On this step, we navigate according to Algorithm A by prescribed edges from one vertex $V$ to some another vertex $V'$.

    We realize the motion mechanically almost in the same way as above: Take any point $P$ lying on the edge connecting $V$ and $V'$ and again realize both $P$ and the convexification $Conv(P)$ as bar-and-joint mechanisms.  Now the polygon $Conv(P)$ is a quadrilateral.  Each of its edge we decompose into small edges of lengths $l_i$. Thus we again have a natural bijection between edges of the two polygons, and the corresponding edges are parallel.  For each pair of parallel edges (one edge from $P$, and the other one from $Conv(P)$), we plug in parallelograms in the same way as we did above. 

    We can assume that the edges of the quadrilateral are frozen, that is, the quadrilateral can flex only at the four vertices. 

    Each (convex) flex of $Conv(P)$ uniquely induces a flex of $P$ in such a way that the first polygon remains the convexification of the second one.  Therefore, the task is to bring the convex polygon $Conv(P)$ from one triangular configuration to another triangular configuration, see Figure \[FigEdge\].  This can be controlled in many ways, since the control of a quadrilateral is well-understood, see [@KHPS]. 

    Important is that every next edge needs a separate collection of auxiliary parallelograms. 

4.   Once we arrive at the point $V_T$, we go to the target point $T$ as on the very first step. 

In our second approach, we again add axillary bars to the polygonal linkage, but now we have one and the same bar-and-joint mechanism which is not rearranged during the desired flex. 

The key observation is that the projection of the 1-skeleton of hypercube can serve as a universal permuting machine: together with any configuration $P$, it contains all other configurations obtained from $P$ by permuting the order of edges, see Figure \[FigHypercube\]. 

On the one hand, an obvious advantage of this approach is that we do not remove and add bars at each step.  On the other hand, a disadvantage is that we need much more extra bars to be added.  Therefore, the choice between the two ways of control depends on the particular practical task. 

**Algorithm C**

1.   We assume that the starting and the target points are $S, \ T\in M(L)$ .  We find the vertices $V_S$ and $V_T$ exactly as in Algorithm B.

2.   Interpret the edges of $S$ numbered $1,2,...,(n-1)$ as projections of edges of the hypercube $[0,1]^{n-1}$. The edge numbered by $n$ is then the projection of the diagonal of the hypercube.  Add extra bars to incorporate $S$ to the entire projection of the hypercube, which is now treated as a bar-and-joint mechanism, see Figure \[FigHypercube\]. 

3.   The new mechanism includes also $Conv(S)$. Now we can manipulate by $Conv(P)$ following Algorithm A. As in Algorithm B, we first bring $Conv(S)$ to the configuration labeled by $V_S=(I,\{1\},J).$

4.   Next, we follow the path on the graph $\Gamma$ prescribed by Algorithm A. For each step, we manipulate with the convex configuration $Conv(P)$ which degenerates to a convex quadrilateral. 

5.   The last step from $V_T$ to $T$ is the same as the very firs step. 

![ Projection of the hypercube includes both $P$ (blue) and $Conv(P)$ (red). []{ data-label="FigHypercube"}](hypercube.eps){width="8"}

[7]{}

M. Farber and D. Schütz, *Homology of planar polygon spaces,* Geom.  Dedicata, 125 (2007), 75-92. 

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

M. Kapovich and J. Millson, *On the moduli space of polygons in the Euclidean plane*, J. Diff.  Geom.,  42 (1995), 430-464. 

G. Panina, *Moduli space of planar polygonal linkage: a combinatorial description*, arXiv:1209.3241 I. Streinu, *Pseudo-triangulations, rigidity and motion planning*, Discrete and Computational Geometry, 34 (2005), 587–635. 

J.-C. Hausmann, *Control of robot arms and Moebius transformations,* arXiv:1304.6214 J.-C. Hausmann and E. Rodriguez, *Holonomy orbits of the snake charmer algorithm*, Geometry and Topology of Manifolds, Banach Center Publications, 76 (2007)

G. Khimshiashvili, *Maxwell problem for polygonal linkages*, Bull.  Georgian Natl.  Acad.  Sci.  6, 2012, No.2, 17-22. 

G. Panina, G. Khimshiashvili, *On the area of a polygonal linkage*, Doklady Akademii Nauk, Mathematics, 85, No.  1 (2012), 120–121. * Coulomb control of polygonal linkages,* arXiv:1304.6214, to appear in J. of Dynamical and Control Systems. , * Cyclic polygons are critical points of area*, Zap. Nauchn.  Semin.  POMI, 360, (2008), 238–245.  G.M. Ziegler, *Lectures on polytopes,* Graduate Texts in Mathematics. ( Springer, Berlin 1995).