I am interested in exploring the degree of "tangledness" of two rigid chains in space. A polygonal chain is a simple (non-self-intersecting) path of segments in $\mathbb{R}^3$, viewed as a rigid body. Think of it as a bent wire in space. Define a move of a chain as either a translation of the whole chain in a fixed direction, or a rotation of the chain about a fixed point axis. I.e., a translation moves each point $p$ of the chain along the path $p(t) = p + t v$ for a fixed direction $v$ as $t$ varies from $0$ to $1$. Say that two chains are separable if there is a sequence of moves during which the chains never touch one another, and eventually end up on opposite sides of a plane.

Q1. If each chain consists of $n$ segments, is there an upper bound as a function of $n$ (and independent of the geometry of the chains) on the number of moves needed to separate a separable pair?

Here is an example for which I believe $O(n)$ moves suffices to separate:

A more focussed question seeks difficult-to-untangle chains:

Q2. Is there a pair of chains that requires $\Omega(n^2)$ moves to separate?

My explorations have not led to an example that clearly requires many moves to separate. For example, I think this pair of spirals also only needs $O(n)$ moves.

A simplification would also be of interest:

Q3. The same questions but with "moves" restricted to translations.

Thanks for ideas or pointers to relevant literature!

  • 1
    $\begingroup$ "rotation about a fixed point" is maybe inappropriate if 3d. It might be rotation about a fixed axis. $\endgroup$ – Günter Rote Feb 24 '13 at 19:48
  • 2
    $\begingroup$ Anyway, When you specify the steps in this form, another important 3-dimensional class of motions is excluded: screw motions (rotation around an axis with simultaneous translation along that axis). Of course such a motion can be approximated by a sequence of translations and rotations, but the number of steps might be large (not bounded in $n$). I imagine two chains that require a screw motion at one point. It would be analogous to allowing a point in the plane to move only vertically or horizontally. The necessary number of such steps inside a slanted strip can be as large as we like. $\endgroup$ – Günter Rote Feb 24 '13 at 19:51
  • $\begingroup$ @Günter: I corrected to rotation about an axis---Thanks! Yes, originally I started to think about mixing translation & rotation. That is more natural, but I tried to simplify. Excellent point about motions in a strip. Thanks for these insights! $\endgroup$ – Joseph O'Rourke Feb 24 '13 at 21:05

Hopefully, someone with better graphics-making ability than me will be able to post a picture of what I'm thinking of (or show that it doesn't work), but here's an attempt to show a pair that require $\Omega(n^2)$ moves.

For now, I'm restricting to translations only.

The first chain is the standard square wave form in the first figure above. For the second chain, take a square spiral on a plane perpendicular to the square wave. The spiral should have largest side length equal to the vertical height of the square wave (so the only way to move a vertical segment through is by pushing it through that one slot. Now, to force the wave to travel the spiral over and over, we add another piece to the second chain. It should be on a plane parallel to the plane of the spiral, and should be a modified square that is just too small for the wave to fit through. We modify the square on the pair of horizontal sides, adding a small detour to each edge, pushing out a small section and adding little extra space, so that the square wave can fit through only if it is centered on the square. Then, line the two up so the center of the square is lined up with the center of the spiral.

Then, the square wave starts going through the center of both parts of the second chain. In order to get each vertical segment through the spiral, we need to go around the spiral to the outside slot, but then to get that vertical segment through the square, we need to spiral back around to the middle.

Does that make sense?

If it does, it seems plausible to me that we'd be able to make 'rotation guards' to add to the second chain, that force us to do those motions even if rotations are allowed, but I'm not sure.

  • $\begingroup$ @Michael: I cannot attempt draw your example now... I am having some difficulty interpreting the phrase "the plane of the spiral." My spirals have an axis, but not a plane. Did you mean the plane perpendicular to the spiral's axis? $\endgroup$ – Joseph O'Rourke Feb 25 '13 at 0:31
  • $\begingroup$ Yes, I meant the plane containing the spiral, perpendicular to the axis. $\endgroup$ – Michael Biro Feb 25 '13 at 1:12

You can twist one wire into a linked double noose (with free endtips):

alt text

If, in turn, you link two of these "loops", the whole thing cannot be unentangled.

  • $\begingroup$ Cute, Rodrigo! But I am only interested in those chains that can be untangled. $\endgroup$ – Joseph O'Rourke Feb 24 '13 at 16:07

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.