# Blowing Up Polygonal Linkages

@article{Connelly2003BlowingUP, title={Blowing Up Polygonal Linkages}, author={Robert Connelly and Erik D. Demaine and G{\"u}nter Rote}, journal={Discrete \& Computational Geometry}, year={2003}, volume={30}, pages={205-239} }

Abstract{Consider a planar linkage, consisting of disjoint polygonal arcs
and cycles of rigid bars joined at incident endpoints (polygonal chains), with
the property that no cycle surrounds another arc or cycle. We prove that the
linkage can be continuously moved so that the arcs become straight, the cycles
become convex, and no bars cross while preserving the bar lengths.
Furthermore, our motion is piecewise-differentiable, does not decrease the
distance between any pair of vertices, and… Expand

#### Topics from this paper

#### 52 Citations

Realization of Simply Connected Polygonal Linkages and Recognition of Unit Disk Contact Trees

- Mathematics, Computer Science
- Graph Drawing
- 2015

It is strongly NP-hard to decide whether a given polygonal linkage is realizable in the plane when the bodies are convex polygons and their contact graph is a tree; the problem is weakly NP- hard already for a chain of rectangles, but efficiently decidable for a chains of triangles hinged at distinct vertices. Expand

Locked and Unlocked Chains of Planar Shapes

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 2010

It is shown that isosceles triangles with any desired apex angle <90° admit locked chains, which is precisely the threshold beyond which the slender property no longer holds, and that a surprisingly general family of planar shapes, called slender adornments, guarantees universal foldability. Expand

Refolding Planar Polygons

- Computer Science, Mathematics
- Discret. Comput. Geom.
- 2009

This paper describes an algorithm for generating a guaranteed intersection-free interpolation sequence between any pair of compatible polygons that builds on prior results from linkage unfolding, and allows additional control by accommodating a set of algebraic constraints that can be weakly enforced throughout the interpolation sequences. Expand

Isometric deformations of planar quadrilaterals with constant index

- Mathematics
- 2014

We consider isometric deformations (motions) of polygons (so-called carpenter's rule problem) in the case of self-intersecting polygons with the additional condition that the index of the polygon is… Expand

Single-Vertex Origami and Spherical Expansive Motions

- Mathematics, Computer Science
- JCDCG
- 2004

It is proved that all single-vertex origami shapes are reachable from the open flat state via simple, non-crossing motions, and the concept of a pseudo-triangulation from the Euclidean to the spherical case is extended. Expand

On the unfolding of simple closed curves

- Mathematics
- 2008

We show that every rectifiable simple closed curve in the plane can be continuously deformed into a convex curve in a motion which preserves arc length and does not decrease the Euclidean distance… Expand

Configuration spaces of convex and embedded polygons in the plane

- Mathematics, Computer Science
- ArXiv
- 2008

This paper concerns the topology of configuration spaces of linkages whose underlying graph is a single cycle. Assume that the edge lengths are such that there are no configurations in which all the… Expand

Convexity-Increasing Morphs of Planar Graphs

- Mathematics, Computer Science
- WG
- 2018

A polynomial time algorithm is given that constructs a morph of any planar straight-line drawing of a 3-connected graph to one with convex faces while maintaining planarity at all times. Expand

Flattening single-vertex origami: The non-expansive case

- Mathematics, Computer Science
- Comput. Geom.
- 2010

Here, the case of open polygons with total length between [@p,[email protected]), which requires non-expansive motions is solved, and the motion planning algorithm works in a finite number of discrete steps, for which the number of links and the angle deficit are given precise bounds. Expand

Convexity-increasing morphs of planar graphs

- Computer Science, Mathematics
- Comput. Geom.
- 2019

A polynomial time algorithm is given that constructs a planar straight-line drawing of a 3-connected graph G to one with convex faces while maintaining planarity at all times, meaning that angles of inner faces never change from convex to reflex. Expand

#### References

SHOWING 1-10 OF 42 REFERENCES

Straightening polygonal arcs and convexifying polygonal cycles

- Mathematics, Computer Science
- Proceedings 41st Annual Symposium on Foundations of Computer Science
- 2000

It is proved that the linkage can be continuously moved so that the arcs become straight, the cycles become convex, and no bars cross while preserving the bar lengths. Expand

Locked and Unlocked Polygonal Chains in Three Dimensions

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 2001

The main result is an algorithmic proof that any simple closed chain that initially takes the form of a planar polygon can be made convex in three dimensions. Expand

Convexifying Monotone Polygons

- Mathematics, Computer Science
- ISAAC
- 1999

It is proved that one can reconfigure any monotone polygon into a convex polygon; a polygon is monot one if any vertical line intersects the interior at a (possibly empty) interval. Expand

Polygonal chains cannot lock in 4d

- Computer Science, Mathematics
- CCCG
- 1999

We prove that, in all dimensions d⩾4, every simple open polygonal chain and every tree may be straightened, and every simple closed polygonal chain may be convexified. These reconfigurations can be… Expand

Reconfiguring closed polygonal chains in Euclideand-space

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 1995

It is shown that in three or more dimensions, reconfiguration is always possible, but that in dimension two this is not the case, and anO(n) algorithm is given for determining whether it is possible to move between two given configurations of a closed chain in the plane. Expand

A note on reconfiguring tree linkages: trees can lock

- Computer Science, Mathematics
- Discret. Appl. Math.
- 2002

It is proved that an N-link tree can have 2 Ω(N) equivalence classes of configurations, and it is shown that there are trees with two configurations that are not connected by a motion. Expand

Convexifying star-shaped polygons

- Mathematics, Computer Science
- CCCG
- 1998

It is shown that all star-shaped simple polygons can be transformed into convex polygons by continuous motions during which the edges remain rigid and the polygon remains star- shaped and simple. Expand

Nonobtuse triangulation of polygons

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 1988

We show how to triangulate a polygon without using any obtuse triangles. Such triangulations can be used to discretize partial differential equations in a way that guarantees that the resulting… Expand

Faster Circle Packing with Application to Non-Obtuse Triangulation

- Mathematics, Computer Science
- Int. J. Comput. Geom. Appl.
- 1997

This work shows how to pack a non-simple polygon with O(n) tangent circles, so that the union of the polygon boundary components and circles is connected, in total time O( n log n), and extends this to a circle packing in which each portion of thepolygon outside the circles is adjacent to at most four circles or boundary edges. Expand

Linear-size nonobtuse triangulation of polygons

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 1995

An algorithm for triangulatingn-vertex polygonal regions (with holes) so that no angle in the final triangulation measures more than π/2, and the running time isO(n log2n). Expand