Unfolding simple chains inside circles

Unfolding Simple Chains Inside Cirles Marzieh Eskandari a , Ali Mohades a a Math. and Computer Siene Dpt., AmirKabir University of Tehnology, P.O.BOX 15875-4413, Tehran, Iran. Abstrat It is an op en problem to determined whether a polygonal hain an be straightened inside a onning region if its links are not allowed to ross. In this paper we prop ose a sp eial ase: whether a polygonal hain an be straightened inside a irle without allowing its links to ross. We prove that this is p ossible if the straightened onguration an t within irle. Then we show that these simple hains have just one equivalene lass of ongurations. Key words: folding, polygonal hain, reonguration 1. Intro dution A hain is a sequene of rigid ro ds or links onseutively onneted at their endp oints, ab out whih they may rotate freely. The link b etween A i  1 and A i (1  i  n ) is denoted by L i and the length of L i is denoted by l i . The angle at intermediate joint A i ,  i 2 [0 ; 2  ), is that determined by rotating L i ab out A i ounterlo kwise to bring L i to L i +1 . The hain  is simple if it is non-self- rossing and non-self-touhing. The subhain of  with joints A i ; :::; A j is denoted by [ i; j ℄. We say a bend operation is p erformed at joint A i , when the joint angle  i is hanged b etween  i and  . Throughout this paper, we assume that the only b end op erations allowed are single-joint b end op erations, in whih only one joint angle is altered at a time. A b end op eration is omplete if, at the end of the op eration the joint angle is  . We then say that the joint has b een straightened . A bend Op eration that is not omplete is alled a partial bend . A sequene of bend op erations is said to b e monotoni if no op eration inreases the absolute deviation from straightness, j  i   j , for a joint A i . Let  = ( i 1 ; i 2 ; :::; i n  1 ) b e a permutation of the indies f 1 ; 2 ; :::; n  1 g . For a simple hain , we say that a sequene ( A i 1 ; A i 2 ; :::; A i n  1 ) of joints is unfoldable , if  an b e straightened into a straight line segment L using the joints in the sequene in Email address: mohadesaut.a.ir (Ali Mohades). turn, suh that  remains simple and all of the b end op erations are omplete. A simple hain  is alled unfoldable hain , if it has a unfoldable sequene of joints. An intermediate joint A i is alled unfoldable joint , if a omplete b end op eration an b e p erformed at A i suh that during the performing b end op eration,  remains simple. The union hain ,  U , of a hain  is a hain whih is obtained from  in the following way: if none of the joints of  is straight joint,  U = ; if  has at least one straight joint, for any straight joints A i , we delete joint A i and put A i  1 A i +1 as a single link. Reonguration problem and in partiular, folding problem, b een raised indep endently by several researhers. [3℄ has onsidered reonguration of rob ot arms inside a irle, with allowing its links to ross. In [4℄, Pei has proved that for a hain  inside a irle whose radius is suÆiently big, there is just one equivalene lass when its links are allowed to ross. In [5℄ and [2℄, straightening a simple hain in the plane is studied and is proved that any simple hain an be straightened in the plane. And in [1℄ Arkin, Fekete and Mithell have given an ef- ient algorithm to determined if a simple hain an b e straightened by p erforming omplete b end op erations. In this pap er, we study straightening a simple hain within a irle. we give a quadrati- time algorithm to straighten a simple unfoldable hain within a irle whose radius is suÆiently big. Then we prove that all of simple hains an 20th EWCG Seville, Spain (2004) 20th Europ ean Workshop on Computational Geometry b e straightened within a irle, if and only if their straightened onguration an t in the irle. Finally we show that any two onguration of these simple hains are equivalent. 2. Preliminaries Let  b e a simple hain inside irle C ( O ; r ) with joints A 0 :::A n . For tting straightened onguration of  in C , we must have P n i =1 l i  2 r . From now on, we suppose  is a simple hain inside C suh that P n i =1 l i < 2 r . For a irle C ( O ; r ) and two p oints x; y 2  C , we use _ xy to denote the lo kwise ar from x to y . For a p oint A i 2  C we denote the other endp oint of the diameter of C whih is ontaining A i , by M i . Denition 1 A joint A r i is al led rim joint if it lies on boundary of irle C . We denote the set of al l rim joints of hain  by A Rim = f A r 0 ; A r 1 ; :::; A r s g . Denition 2 For any rim joint A i of hain  , the vetor ! O M i is al led radius vetor of A i and is denoted by r i . Lemma 3 There is a diameter s = ab of irle C suh that al l of rim joints of hain  belong to one of the ars _ ab or _ ba . PROOF. If A Rim = ; , there is nothing to prove. Let A i b e a rim joint of  and X b e a moving ob jet whih is walking along ar _ A i M i lo kwise, starting at the p oint A i . Supp ose A r is the last rim joint of  that is visited by X . Diameter s = A r M r is a solution. Beause ar _ A r M r ontains no rim joint of , exept A r . 2 Denition 4 Suppose A Rim has at least two point and rim joints of  belong to _ ab . The nearest rim joints to points a and b are denoted by A f and A e , respetively. These joints are al led limit-joints . It is lear that all of the other rim joints of  are on ar _ A f A e . Denition 5 Let A e and A f be limit-joints of  . Vetors r e and r f are al led diretion vetors . Denition 6 The sum of diretion vetors, r e and r f , is al led entral diretion and denoted by d , i.e., d = r e + r f . Central Translation: We draw n vetors parallel to d from any joint A i until hit irle at points N i , then put " i = jj ! A i N i jj and " = min f " i j 0  i  n g . Translation of  inside C along the vetor d " = " jj d jj d , is alled entral translation of . New p ositions of  and any joint A i , after the entral translation, are denoted by  0 and A 0 i . It is lear that " e = " f . 3. Unfoldable Simple Chains Supp ose  = ( A i 1 ; A i 2 ; :::; A i n  1 ) is an unfoldable sequene of joints of . For straightening  inside irle C ( O ; r ), we prop ose the following algorithm whih ontains three steps: Algorithm 1 Unfolding Simple Chain  : step 1.  0 =  ; j = 0 . step 2.  0 =  0 U ; j = j + 1 . If j = n , stop. else k = i j ; step 3. Straighten A k . Go to step 2. Now for step 3, straightening joint A k within ir- le C , we prop ose the following algorithm whih ontains four steps: Algorithm 2 Straightening joint A k : step 1.  0 = [0 ; k ℄ ;  n = [ k ; n ℄ ; step 2. Rotate  0 about A k until A k straightens or one of joints of  0 hits C and  0 an not rotate more about A k . If A k straightens, stop; else go to step 3. step 3. Rotate  n about A k until A k straightens or one of joints of  n hits C and  n an not rotate more about A k . If A k straightens, stop; else go to step 4. step 4. Calulate d " and transmit  by d " . Go to step 2. 4. Corretness of Algorithm 2 Any rep eat of algorithm 2 is alled a phase and the joint angle at A k , at the end of phase i , is denoted by  i . For showing orretness of algorithm 2, we show that during the algorithm,  remains simple and it remains inside C . And we prove that by using algorithm 2, after a nite numb er of rep eats, A k straightens. Furthermore, this nite numb er is indep endent of n . Chain  remains simple, b eause A k is an unfold- Marh 25-26, 2004 Seville (Spain) able joint in the plane. Now for showing that  remains inside C , we rst prove that entral translation always an be done. Lemma 7 d " 6 = 0 . PROOF. If d = 0 , we have r f =  r e . That is implies A f = M e and A e = M f , i.e., A f A e = 2 r . Therefore P n i =1 l i  P l i 2 [ e;f ℄ l i  A f A e = 2 r . That is a ontradition. Thus d 6 = 0 . Beause the angles b etween d and its omp onents are less than  = 2 and all of radius vetors lie b etween vetors r e and r f , the angle b etween d and radius vetors are less than  = 2, to o. Thus any rim joint an transmit in diretion d inside C . Any interior p oints of C also an transmit in all diretions inside C . Therefore " 6 = 0. Consequently d " 6 = 0 . 2 It is lear that during the step 1 and step 2, all of the joints remain inside irle. At step 3, b eause " = min f " i j 0  i  n g and the angle b etween radius vetors and d are less than  = 2,  remains inside C . Now to show that after a nite number of rep eats, algorithm 2 is terminated, we rst show that at the end of any phase of algorithm 2,  i b eomes strongly lose to  , i.e., j    i +1 j < j    i j . So we have to prove at the end of entral translation of , at least one of the sub hains  0 or  n , an rotate ab out A k suh that joint angle at A k has b eame lose to  . Note that at the end of step 1 and step 2, if A k do es not straighten, A Rim has at least two points, one p oint from  0 and the other p oint from  n . Lemma 8 Let A e and A f be the limit-joints of  at phase i. If both of A e and A f belong to one of the subhains  0 or  n , then at the end of translation, none of the joints of the other subhain lie on  C . Furthermore, this subhain an rotate about A k at phase i + 1 . PROOF. Assume without loss of generality that A f ; A e 2  0 . Supp ose for a ontradition, A t is a joint of  n suh that A 0 t 2  C . At the b eginning of translation,  n has at least one rim joint, A m , whih lies on ar _ A f A e . If A k is in the exterior of losed urve Æ = _ A f A e [  0 [ e; f ℄,  n [ m; k ℄ and  0 [ e; f ℄ will b e interseting. Thus A k is in the interior of Æ . See gure 1. Therefore A 0 k is in the interior of the losed urve Æ 0 =  [  0 0 [ f ; e ℄ where Af Af - Ae Ae - Ak - Ak Am d G - A0 G b Fig. 1. If  n ontains no limit-joints,  0 n has no rim joint.  is the translation of ar _ A f A e by the vetor d " . But A 0 t is in the exterior of Æ 0 . So  0 n [ k ; t ℄ intersets b oundary of Æ 0 . That is a ontradition. Beause  n [ k ; t ℄ do es not interset boundary of Æ . 2 By lemma 8, we suppose A e and A f don't b elong to the same sub hain. From now on, the subhain whih ontains A e is denoted by  e and the other sub hain whih ontains A f is denoted by  f . We have the following theorem. Theorem 9 At the end of translation, at least one of the subhains  e and  f an rotate about A k . PROOF. Refer to full pap er. 2 Corollary 10 j  i   j > j  i +1   j . By orollary 10, the onguration of  in two onseutive phase is dierent. Thus during the algorithm 2, straightening A k is strongly progressed and yling is not p ossible. Now for showing that after a nite number of rep eats, algorithm 2 is terminated, we use simpliity of . Assume without loss of generality that  k <  . Thus aording to denition of joint angle,  0 must rotate ab out A k lo kwise. First supp ose there is no onning region. So A k an b e straightened and then  0 an rotate ab out A k lo kwise more, until rst selftouhing is o urred. This op eration is alled  - passage motion and the joint angle at A k is denoted by  +  k , that  k > 0. Now suppose  is inside C ( O ; r ). We hange the stopping riteria of algorithm 2, from ahieving  to ahieving  +  k and use this new algorithm on A k . All of ab ove pro ofs also hold for this new algorithm. So by orollary 10 we also have: j  i +1     k j < j  i     k j (  ) 20th Europ ean Workshop on Computational Geometry Assumption  k <  yields: for every i  0,  i   +  k . So (  ) yields  +  k   i +1 <  +  k   i . In the other words, f  i g i  0 is a bounded and monotone sequene. Therefore it onverges to its suprimum,  +  k . Thus for every " > 0 exists a nite natural numb er N > 0 suh that for every i  N we have j  i     k j < " , i.e., for every i  N ,  +  k   i < " . Thus for " =  k , there is a nite numb er N  suh that for all i  N  ,  +  k   i <  k . So for i = N  , we have  +  k   N  <  k , i.e.,  N  >  . Beause N  is the smallest natural numb er that  +  k   i <  k , we have  +  k   N   1   k , i.e.,  N   1   . Therefore A k an straighten in phase N  or N   1. Beause  N   1   and  N  >  . It is lear that N  is indep endent of n . Therefore proof of orretness of algorithm 2 is terminated. Complexity of algorithm 1 is O ( n 2 ), b eause omplexity of eah step is O ( n ) and the numb er of rep eats is n  1. 5. Arbitrary Simple Chains Now we prove that an arbitrary simple hain an b e straightened inside a irle. First we have the following theorem. Theorem 11 Any simple hain  an be straightened using a nite number of monotoni singlejoint bend operations. PROOF. See [1℄ and [2℄. 2 Theorem 11 is true, if hain is inside a irle as a onning region. Theorem 12 A simple hain  an be straightened inside a irle using a nite number of monotoni single-joint bend operations, if n X i =0 l i < 2 r . PROOF. By theorem 11,  an be straightened in the plane using a nite numb er of monotoni single-joint b end op erations. If all of these b end op erations are omplete,  an be straightened by using algorithm 1. But if at least one of the b end op erations is not omplete, these b end op erations will b e in aordane with a sequene of motions, M = f M j g k j =1 , suh that M j is a partial bend op eration and  an be straightened by using M . Any op eration M j is single-joint, so it is in aordane with a joint A i j and this aordane is not one to one, b eause M j s are not omplete. Supp ose any bend operation M j is hanged joint angle at A i j by ( A i j ; j ). Now note that any op eration M j is monotone; so if we hange the stopping riteria of algorithm 2, from ahieving  to ahieving  i j + ( A i j ; j ), this new algorithm an be used to p erform any b end op eration M j inside C . Therefore  an b e straightened inside C by p erforming M j s in turn, b eause k is nite. 2 6. Conlusion Assume that  is a simple hain suh that P n i =1 l i < 2 r and  1 and  2 are two onguration of  inside irle C ( O ; r ). We denote their straight ongurations by L 1 and L 2 , resp etively. Let M b e a sequene of bend op erations for straightening  2 inside C and M R b e the reverse of Motion M . It is lear that by p erforming M R , L 2 an b e reongured to  2 . Now by theorem 11, we an reongure  1 to L 1 , then we an reongure L 1 to L 2 by translation and rotation operations and nally we an reongure L 2 to  2 by M R . So  1 an b e reongured to  2 inside C , i.e., for a simple hain , if n X i =1 l i < 2 r , then any two ongurations of , inside irle C ( O ; r ) are equivalent. Referenes [1℄ E.M. Arkin, S.P. Fekete and J.S.B. Mithelle, An algorithmi study of manufaturing pap erlips and other folded strutures. Computational Geometry: Theory and Appliations 25 , 117-138, (2003). [2℄ R. Connelly, E.Demaine and G. Rote, Every polygon an b e untangled. In Pro. 41st Annu. IEEE Sympos. Found. Comput. Si. , pp. 432-442, (2000). [3℄ J. Hop roft, D. Josehp, and S. Whitesides, On the movement of rob ot arms in 2-dimensional bounded regions. SIAM J. Compt. 14 , 315-333, (1985). [4℄ N. Pei, On the reonguration and reahability of hains. Ph.D. Thesis, Shool of Computer Siene, MGill University, November, 1996. [5℄ I. Streinu, A ombinatorial approah to planar non- olliding rob ot arm motion planning. In Pro. 41st Annu. IEEE Sympos. Found. Comput. Si. , pp. 443- 453, (2000).