Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 42 (2001), No. 2, 301-306.

A New Class of Stuck Unknots in Pol_{6}

Godfried Toussaint

School of Computer Science, McGill University 3480 University Street, Montreal, Quebec Canada H3A 2A7 e-mail: godfried@cs.mcgill.ca

Abstract. We consider embedding classes of hexagonal unknots with edges of fixed length. Cantarella and Johnston [3] recently showed that there exist “stuck” hexagonal unknots which cannot be reconfigured to convex hexagons for suitable choices of edge lengths. Here we uncover a new class of stuck unknotted hexagons, thereby proving that there exist at least five classes of nontrivial embeddings of the unknot. Furthermore, this new class is stuck in a stronger way than the class described in [3] .

1. Introduction

A closed chain of n line segments with lengths l_{1}, …, l_{n} embedded in R^{3} forms a space polygon. The space of such polygons is denoted (using the notation of Cantarella and Johnston [3]) by Pol_{n}(l_{1}, …, l_{n}). We are concerned here with simple space polygons or unknots (also trivial knots). Recently Cantarella and Johnston [3] and independently, Biedl et al. [1] studied the embedding classes of such objects and discovered that there exist stuck (or locked) simple polygons. The polygon of Biedl et al. [1] contains 10 edges whereas the example of Cantarella and Johnston [3] has only six edges (see Figure 1). Here we can view the polygon as an idealized linkage where the edges of the polygon are rigid bars, the vertices are universal joints, and no two edges are allowed to cross each other during any continuous reconfiguration of the polygon. These results are relevant to understanding how small-scale rigidity influences the shape of DNA and other complex molecules [9], [6], and are also of interest to linkage convexification problems because they imply there exist linkages in 3D that cannot be convexified.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 2001 Heldermann Verlag

302 G. Toussaint: A New Class of Stuck Unknots in Pol_{6}

Figure 1. The stuck unknot of Cantarella and Johnston

A particularly attractive elementary and simple motion frequently used in polymer physics [13] is the pivot. Two vertices u and v of a polygon P partition the polygon into two chains. A pivot is a rotation of one of these chains about the line containing u and v which acts as the axis of rotation. Linkages in 3D that are planar and simple can be convexified with a finite number of pivots by an angle of π [14], [7], [12] while maintaining simplicity during the motions. Independently, Grünbaum and Zaks [8] and Bernd Wegner [15] also showed that planar polygons with self-intersections can be convexified with a finite number of pivots. The algorithm in [8] takes O(n^{2}) time per pivot in the real RAM (Random Access Machine) model of computation. A simpler approach for crossing polygons that takes only O(n) time per pivot is proposed in [12]. Furthermore, with more complicated motions such as linetracking motions simple planar polygons in three dimensions can be convexified in O(n) moves [1] without crossings.

If we restrict ourselves to simple polygons in two dimensions then the problem of whether every polygon can be convexified without allowing crossings, also known as the carpenter’s ruler problem, was open for more than a decade until in the year 2000 it was finally solved by Connelly, Demaine and Rote [5]. Further computational simplifications on this problem have been obtained by Streinu [11]. Note that in the two-dimensional problem the motions have to remain in the plane. In four and higher dimensions Cocan and O’Rourke [4] showed that all polygons can be convexified without crossings.

Returning to the locked hexagon example of Cantarella and Johnston [3] illustrated in Figure 1, since, in addition to the flat convex version, there are “right” and “left” handed versions of the unknot, Cantarella and Johnston in effect proved that the space of isotopic embeddings has at least three connected components. We remark that the lengths of the edges are crucial for this property to hold. Indeed, if all six lengths are the same, Millet and Orellana [10] showed that the class of unknots in Pol_{6}(1, 1, 1, 1, 1, 1) is connected. Furthermore, if we consider orientation Calvo [2] has shown that there are distinct embeddings of left and right-handed trefoils in Pol_{6}(1, 1, 1, 1, 1, 1). In the conclusion of their paper Cantarella and Johnston state that they suspect that all stuck unknots in Pol_{6} belong to the class illustrated in Figure 1, in other words, that there are no more than three components in Pol_{6}. In this note we describe a new class of stuck unknotted hexagons and show that this class is stuck in a stronger sense than the class exhibited in [3]. An example of such a hexagon in this new class is illustrated in Figure 2.

Figure 2. A new class of stuck unknotted hexagons

2. A new stuck unknotted hexagon

Denote the space polygon by its vertices A = A_{1}A_{2} ⋯ A_{6} and let l_{i} be the length of link A_{i}A_{i+1}, modulo 6. Note that the lengths in both figures are not metrically accurate but the figures are easier to visualize as shown. For our new class we could in fact use the same lengths as Cantarella and Johnston do and in the same order. However, it makes the argument simpler if we change them. Accordingly let the lengths be: l_{1} = 20, l_{2} = l_{6} = 13, l_{3} = l_{5} = 4 and l_{4} = 1. The argument follows directly from the results on stuck chains of five segments (the “knitting-needles”) obtained in [3] and [1].

The only way to flatten the polygon with the knot diagram shown is to either pass the chain A_{3}A_{4}A_{5}A_{6} over A_{1} or under A_{2}. For this to occur it is necessary that the length of A_{3}A_{4}A_{5}A_{6} be not smaller than the length of the shorter of l_{2} and l_{6} or 13. But the length of A_{3}A_{4}A_{5}A_{6} is 9 < 13. This condition is sufficient for the polygon with the knot diagram shown in Figure 2 to be stuck. First we show that such a knot diagram can be realized by a hexagon. There is considerable leeway in such constructions and we will just outline one such strategy for actually obtaining coordinates. First construct a crossing planar polygon on the xy-plane with the given link lengths such that the distance between the parallel links A_{1}A_{2} and A_{4}A_{5} is 1. Denote the height (z-coordinate) of each vertex by h_{i} and refer to Figure 3. The final polygon will have vertices A_{1}, A_{2}, A_{3} on the xy-plane (shaded triangle) and thus height zero. Now select some positive real number ϵ as small as desired, say less than 0.1, and let h_{4} = +ϵ and h_{5} = −ϵ. Link A_{3}A_{4} is now fixed and above the xy-plane, where A_{4} has height +ϵ. The length of link A_{3}A_{4} is adjusted accordingly. Vertex A_{5} is now fixed at height −ϵ and the length of link A_{4}A_{5} is adjusted accordingly. Construct the line segment from A_{5} with z-coordinate −ϵ through link A_{2}A_{3} until it intersects the vertical line L_{6} that contains A_{6} at δ′. Now check if A_{1}δ′, which lies above the xy-plane by construction, also lies below link A_{3}A_{4}. If it does choose h_{6} = (δ′)/2. If it lies above link A_{3}A_{4} lower the line (at A_{6}) until it lies below link A_{3}A_{4} and choose the corresponding height for A_{6}, adjusting the length of link A_{1}A_{6} accordingly.

An example of a polygon with the knot diagram shown in Figure 2 and which is stuck, has the following coordinates. A_{1} = (100, 10, 0), A_{2} = (−100, 10, −1), A_{3} = (10, 20, 0), A_{4} = (10, 0, 10), A_{5} = (−10, 0, −10), A_{6} = (−10, 20, 0).

For completeness we review the proof that the “knitting needles” are stuck. We include the proof of Biedl et al. [1] because it is simpler and shorter than the proof in [3]. Let

Figure 3. One construction strategy for the polygon with the required knot diagram

C = A_{0}, A_{1}, …, A_{5} be a polygonal chain of five links with lengths l_{1}, l_{2}, …, l_{5}, respectively. There is no problem making the first and last links each to be greater than twice the sum of the lengths of the other three links. Finally let the “knot” diagram of C be as illustrated in Figure 4. Then we have the following lemma.

Lemma 1. ([3], [1]) The “knitting needles” cannot be straightened.

Proof. Construct a ball of radius r = l_{2} + l_{3} + l_{4} centered at A_{1} and keep link A_{0}A_{1} fixed as a reference frame during any untangling motion of the remaining links. Because l_{1} and l_{5} are each more than twice the length of r, it follows that A_{0} and A_{5} must stay outside the ball at all times during any motion. Therefore we can attach a chain of small enough segments C′ between A_{0} and A_{5} such that C′ lies outside the ball and such that the knot diagram of the union of C and C′ is the trefoil knot. Now assume that C can in fact be straightened. Since C′ remains outside the ball and A_{1}A_{2}A_{3}A_{4} remains inside the ball at all times during the untangling motion it follows that if C were straightened then the union of C and C′ would be the unknot, which contradicts the fact that it is a trefoil knot. □

This lemma immediately implies that the unknotted hexagon of Figure 2 cannot be convexified. For if a link is removed from the polygon it can only help to untangle the remaining chain. To this end let us remove link A_{1}A_{2}. But this results in the “knitting-needle” example which is stuck. Therefore the polygon is also stuck and cannot be reconfigured into a convex polygon. The lemma also shows that the hexagon of Figure 2 cannot be reconfigured to the hexagon of Figure 1. For assume that it can and again remove link A_{1}A_{2} before such a reconfiguration is carried out. Then certainly the resulting chain can be reconfigured accordingly even more easily. Examining chain A_{2}, A_{3}, …, A_{6}, A_{1} in Figure 1, with A_{1}A_{2} missing, we see that A_{1}A_{6} can be rotated about A_{6} in the plane determined by A_{1}A_{6}A_{5} to straighten A_{6}. Thus we obtain a polygonal chain with four links. But by Lemma 2 in [3] all polygons in space with less than five links can be straightened. But this implies that the polygon in Figure 2 with A_{1}A_{2} missing can be straightened and this contradicts the “knitting-needle” lemma.

3. Concluding remarks

It is clear from the example in Figure 2 that here we also have left and right handed versions of the polygon. In conclusion we can state the following result.

Figure 4. The “knitting-needles” example of a stuck chain of five segments [3], [1]

Theorem 1. For suitable choices of edge-length, there are at least five classes of embeddings of the unknot in Pol_{6}.

Just as in the example of Cantarella and Johnston, we can obtain a family of stuck unknots similar to the polygon in Figure 2 for any value of n > 6 by inserting a polygonal chain of any number of edges between A_{4} and A_{5} as long as their total length does not exceed the length l_{4}.

Finally we remark that the hexagon in Figure 2 is in a sense more stuck than the hexagon in Figure 1. Let us define the stuck number of a polygon as the minimum number of links that must be removed so that the remaining open chains can be straightened. Then, if the stuck number of a polygon is k we will say the polygon is k-stuck. Let us call a polygon weakly k-stuck if the removal of any k links allows the remaining open chains to be straightened. Similarly, let us call a polygon strongly k-stuck if this is not the case but there exists some set of k links whose removal allows subsequent straightening. From the results of Cantarella and Johnston [3] it follows that the hexagon in Figure 1 is weakly 1-stuck whereas the example in Figure 2 is strongly 1-stuck. Indeed, we have just seen that if in the hexagon of Figure 2 the link A_{1}A_{2} is removed we obtain the stuck knitting-needles example of Cantarella and Johnston [3] and Biedl et al. [1]. This suggests an interesting open problem: given a space polygon P consisting of n edges, what is the complexity of determining the stuck-number of P?

References

[1] Biedl, T.; Demaine, E.; Demaine, M.; Lazard, S.; Lubiw, A.; O’Rourke, J.; Overmars, M.; Robbins, S.; Streinu, I.; Toussaint, G. T.; Whitesides, S.: Locked and unlocked polygonal chains in 3d. In: Proc. 10th ACM-SIAM Symposium on Discrete Algorithms, 1999, 866–867.

[2] Calvo, Jorge A.: The embedding space of hexagonal knots. To appear in: Topology and its Applications 110(2) (2000).

[3] Cantarella, Jason; Johnston, Heather: Nontrivial embeddings of polygonal intervals and unknots in 3-space. Journal of Knot Theory and its Ramifications 7(8) (1998), 1027– 1039.

[4] Cocan, Roxana; O’Rourke, Joseph: Polygonal chains cannot lock in 4d. In: Proc. 11th Canadian Conference on Computational Geometry, 1999.

[5] Connelly, Robert; Demaine, Erik; Rote, Gunter: Straightening polygonal arcs and convexifying polygonal cycles. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science. Redondo Beach, California, November 12–14 2000.

[6] Frank-Kamenetskii, Maxim D.: Unravelling DNA. Addison-Wesley 1997.

[7] Grünbaum, Branko: How to convexify a polygon. Geombinatorics 5 (1995), 24–30.

[8] Grünbaum, Branko; Zaks, Joseph: Convexification of polygons by flips and by flipturns. Technical Report 6/4/98, Dept. of Mathematics, University of Washington, Seattle 1998.

[9] Holden, C.: Random samples: Locked but not knotted. SCIENCE 283, February 12, 1999, 931.

[10] Millet, K.: Knotting of regular polygons in 3-space. Journal of Knot Theory and its Ramifications 3 (1994), 263–278.

[11] Ileana Streinu. A combinatorial approach to planar non-colliding robot arm motion planning. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science. Redondo Beach, California, November 12–14 2000.

[12] Toussaint, Godfried T.: The Erdős-Nagy theorem and its ramifications. In: 11th Canadian Conference on Computational Geometry. Vancouver, Canada, August 16-18 1999, 9–12. Long version available at: http://www.cs.ubc.ca/conferences/CCCG.

[13] Janse van Rensburg, E. J.; Whittington, S. G.; Madras, N.: The pivot algorithm and polygons: results on the FCC lattice. Journal of Physics A: Mathematical and General Physics 23 (1990), 1589–1612.

[14] Wegner, Bernd: Partial inflation of closed polygons in the plane. Beiträge Algebra Geom. 34(1) (1993), 77–85.

[15] Wegner, Bernd: Chord-stretched convex versions of planar curves with self-intersections. Technical report, Department of Mathematics, Technical University of Berlin 1999.

Received July 16, 1999