Ok, so I try to formulate rigorously the question in the title, for which I am asking for references. My definitions may be flawed, so feel free to adjust/correct them! I care about dimensions 2 and 3 below, but feel free to mention general d as well.

Let $d\ge 1$ be an integer, $G=(V,E)$ be a graph, $w:E\to [0, \infty)$ be a weight function. A realization in $\mathbb R^d$ with graph $G$ and weight $w$ is a map $P:V\to\mathbb R^d$ with the further property that $|P(v)-P(v')|=w(v,v')$ whenever $\{v,v'\}\in E$. I will identify such $P$ with its image, I hope it's not a problem.

Edit (May 11, 2020): As pointed out by Misha, this below definition is not correct. The action of isometries makes the set of all realizations of a linkage always cover all $\mathbb R^d$. He indicates a paper in which a more inclusive definition is formulated in $d=2$.

(Previous "wrong" definition: I say that a set $A\subset \mathbb R^d$ is realizable by linkages if there exists $G,w$ as above and an cover of $A$ by open sets of $\mathbb R^d$ such that for every $U\subset\mathbb R^d$ in the cover there exist $G,w$ such that that the union of all (images of) realizations of $G,w$ in $\mathbb R^d$ intersected with $U$ coincides with $A\cap U$.)

To "fix the problem", following the we will allow a subset of vertices of $G$ to be kept fixed in $\mathbb R^d$. In dimension $2$ this apparently generalizes the definition in the above paper, but I think that the result of the paper still allows to reply positively to the $d=2$ case of the question, with little extra work.

Revised definition: We say that $A\subset \mathbb R^d$ is realizable by linkages if there exists a cover of $A$ by open sets of $\mathbb R^d$ such that for every $U\subset\mathbb R^d$ in the cover there exist $G=(V,E)$ and $w$ as above, a subset $F\subset V$, and a map $\phi: F\to\mathbb R^d$, such that the union of all (images of) those realizations of $G,w$ which restricted to $F$ equal $\phi$, intersected with $U$, coincides with $A\cap U$.

Question: Say $d=2$ or $d=3$. Is it true that all algebraic sets $A\subset\mathbb R^d$ are realizable by linkages? What are references for this?

(Note: as of May 11 2020, it appears to me that the case $d=2$ is nicely treated in the answers given, while the case $d=3$ is not yet treated, possibly due to the previously bad definition.)

I found some mention of this, without references on Branko Grünbaum's "Lectures on lost mathematics", dated around 1975, and he says there that $d=2$ case is known, but does not give references, and $d=3$ case is a question by Hilbert which is open (but again no references there).

  • 1
    $\begingroup$ Your definition of a realizable set is wrong: With this definition, the only realizable subsets are the open subset of ${\mathbb R}^d$. See here for precise definitions. $\endgroup$
    – Misha
    May 8 '20 at 18:58
  • $\begingroup$ Thank you Misha, I will edit the question! $\endgroup$
    – Mircea
    May 11 '20 at 21:49

Thurston sketched a proof that any real algebraic set is a component of the configuration space of a planar linkage. Kapovich and Milson gave a full proof. Check out this paper by Henry King which gives some history.



Erik Demaine and I also included a proof for $d=2$ in Geometric Folding Algorithms: Linkages, Origami, Polyhedra, Chapter 3. There we asked if there is a planar (non-crossing) linkage that "signs your name" (traces any semi-algebraic region), a question posed by Don Shimamoto in 2004.

This was recently settled positively by Zachary Abel in his Ph.D. thesis: any polynomial curve $f(x,y) = 0$ can be traced by a non-crossing linkage.

Abel, Zachary Ryan. "On folding and unfolding with linkages and origami." PhD diss., Massachusetts Institute of Technology, 2016. MIT link.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.