A quadratic distance bound on sliding between crossing-free spanning trees

A quad a ic dis ance bound on sliding be ween c ossing- ee spanning ees Oswin Aichholze a,1and Klaus Reinha d b aIns i u e o So wa e echnology G az Uni e si y o Technology, Aus ia bWilhelm-Schicka d-Ins i u ¨u In o ma ik Uni e si ¨a T¨ubingen, Ge many Abs ac Le Sbe a se o npoin s in he plane and le TSbe he se o all c ossing- ee spanning ees o S. We show ha any wo ees in TScan be ans o med in o each o he by O(n2) local and cons an -size edge slide ope a ions. No polynomial uppe bound o his ask has been known, bu in [1] a bound o O(n2log n) ope a ions was conjec u ed. Key wo ds: c ossing- ee spanning ee, local ans o ma ion, edge slide 1. In oduc ion Le Sbe a se o npoin s in he Euclidean plane. W.l.o.g. we assume ha no wo poin s o Sha e he same x-coo dina e, o he wise we o a e he coo - dina e sys em app op ia ely. A c ossing- ee span- ning ee o Sis a ee whose edges connec all poin s in S(and no o he s) wi h s aigh line seg- men s ha pai wise do no c oss. Wi h TSwe de- no e he se o all c ossing- ee spanning ees o S. An in e es ing ques ion is whe he , and how as , wo membe s o TScan be ans o med in o each o he by means o p ede ined ules, o en called lips. A common ope a ion is wha is called an edge mo e, which ela es wo ees in he se TSi hey ha e all bu one edge in common (one edge is ‘ lipped’). Fo his gene al se ing A is and Fukuda [2] showed ha he co esponding ee g aph is connec ed and has a diame e bounded by 2n−4. I we es ic he se o allowed lips o plana , leng h-imp o ing edge mo es hen in [1] a way o ans o m any ee T∈ TSin o he mini- Email add esses: oaich@is . ug az.a (Oswin Aichholze ), einha d@in o ma ik.uni- uebingen.de (Klaus Reinha d ). 1Resea ch suppo ed by Acciones In eg adas 2003-2004, P oj.N .1/2003 mum spanning ee o Sin only O(nlog n) s eps was gi en. Fo a mo e de ailed discussion and some his o ical backg ound see [1]. Ou in e es is ocused on a local edge mo e ha keeps one endpoin o he mo ed edge ixed and mo es he o he one along an adjacen ee edge. Following [3], we will call his cons an -size ope a- ion an edge slide. Mo e o mally he cen al ope - a ion we conside is de ined as ollows [1]: Conside a ee T′∈ TS. A (plana ) edge slide on T′ akes some edge e∈T′and mo es one o i s endpoin s along some edge adjacen o ein T′, wi hou gen- e a ing any edge c ossings. This gi es a new edge and a new ee T′′ =T′∪ { } {e}such ha T′′ ∈ TS. An edge slide is a special kind o plana edge mo e: T′′ is ob ained by closing wi h a 3- cycle Cin T′and by emo ing e om C, in a way such ha T′a oids he in e io o he iangle C. In ui i ely speaking, an edge slide is an edge ope - a ion as local as i can be. In his pape we in es iga e he ques ions o how as wo c ossing- ee spanning ees o TS can be ans o med in o each o he by means o he edge slide ope a ion. To his end conside he ee g aph TG(S) which is an undi ec ed g aph ha has TSas i s se o nodes. I ealizes an a c be ween wo nodes ( ees) T′and T′′ i and only 20 h EWCG Se ille, Spain (2004) 20 h Eu opean Wo kshop on Compu a ional Geome y i T′can be ans o med in o T′′ by an edge slide (and ice e sa). In [1] i was shown ha TG(S) is connec ed. The leng h o a sho es pa h in TG(S) co esponds o he dis ance be ween he wo espec i e ees. Howe e , o he edge slide ope a ion no polynomial uppe bound on his leng h has been known. I was conjec u ed ha ‘i wo ees a e pa o he same iangula ion o S hen hey can be ans o med in o each o he by O(n2) edge slides’. By esul s in [1], his would gi e a diame e o O(n2log n) o he co espond- ing ee g aph TG(S). We a e able o p o e he ollowing, s onge esul : Theo em 1 Le T′and T′′ be any wo c ossing- ee spanning ees o S. Then T′can be ans- o med in o T′′ by O(n2)edge slides. As men ioned in [1] he edge slide ope a ion could also p o e use ul in enume a ing all simple polygons on a poin se S ia cons an -size local ans o ma ions. This ques ion is s ill unse led; see e.g. He nando e al. [5]. Ou uppe bound on he diame e o TG(S) migh be use ul in his espec . 2. Uppe Bound Cons uc ion Le Sand T∈ TSbe as de ined in Sec ion 1. We call a pai (e, pj), whe e e=pipkis an edge o Tand pi, pj, pk∈Sa e so ed in x-o de , a slide iangle i he open iangle ∆ = pipjpkis ee o poin s om Sand edges om T, ha is, he in e- io o ∆ is emp y. q e’ e’’ p p’ p’’ (e’,p) Fig. 1. A slide iangle (e′, p), see Lemma 2. Lemma 2 Le Pbe a simple polygon wi h e ex se S, and le δP be he bounda y o Pwi h one ma ked edge e∗. I δP {e∗}is no x-mono onous pa h hen in he in e io o P he e always exis s a slide iangle (e, p)⊂P,e6=e∗. P oo Since δP {e∗}is no x-mono onous he e exis s a e ex q∈Swi h wo edges om δP {e∗}bo h emana ing o he same side, i.e., bo h o he le o igh o q. Le e′and e′′, e- spec i ely, be hese edges. W.l.o.g. we assume ha hey emana e om q o he le , e′lies below e′′ and he le endpoin p′o e′lies o he le o he le endpoin p′′ o e′′, see Figu e 1 (all o he cases a e symme ic). I he open iangle ∆ = qp′p′′ is emp y we ha e a slide iangle (e′, p′′). O he wise conside he poin pwhich among all poin s o P in he in e io o ∆ minimizes he angle ∠pp′qa p′. No e ha he e a e no edges (pa ially) inside ∆ ha ha e qas an endpoin o in e sec e′o e′′. The e o e pp o ides a slide iangle (e′, p). ✷ (a) (b) (c) Fig. 2. Cu ing a ee polygon (a) along in e io edges (b) o ob ain a simple polygon (c). A ee polygon Pis a simple polygon wi h in e- io poin s, each poin connec ed o he bounda y δP ia a unique (simple) pa h such ha he esul - ing g aph is plana , see Figu e 2(a). In o he wo ds, he g aph wi hou he edges o δP is a o es . We claim ha we can handle his mo e gene al si ua- ion like a simple polygon: Cu along in e io edges and mo e hem apa a he cu s in ini esimally, i.e., duplica e he ela ed e ices, see Figu e 2(b) and (c). Obse e ha he p oo o Lemma 2 s ill holds o his se ing by conside ing edges e′and e′′ ha a e neighbo ing in he cyclic o de a ound q. We call he x-mono onous pa h connec ing all e ices o Sin hei x-so ed o de he canonical spanning ee Tc∈ TSo S. Theo em 3 Fo a poin se Sand a c ossing- ee spanning ee T∈ TS,T6=Tc, he e always exis s a slide iangle (e, p),p∈Sand e∈Tsuch ha he pa h π∈Tconnec ing p o e, say a poin q, is x-mono onous. Mo eo e π∪pq is a simple poly- gon wi hou in e io poin s. Ma ch 25-26, 2004 Se ille (Spain) P oo We i s show ha he e always exis s some slide iangle (e, p). The union o Tand he bound- a y o he con ex hull o Spa i ions Sin o k≥1 ee polygons Pi,i= 1,...,k. Since Tis a con- nec ed spanning ee each Pihas a unique edge which s ems om he bounda y o he con ex hull o S. We ma k hese edges. F om Lemma 2 and he discussion a e wa ds we know ha we ge a slide iangle inside some Piunless o all Pi he emain- ing (non ma ked) pa is x-mono onous. Bu in he la e case Tmus be x-mono onous, oo, ha is, T=Tc, a con adic ion. e p q π P Fig. 3. A pa h πconnec ing p o q. Le qbe he ( i s ) endpoin o e o which p is connec ed. I he edge pq belongs o Twe a e done. Thus assume ha pis connec ed o q ia a pa h πo leng h g ea e han 1, see Figu e 3. Since (e, p) is a slide iangle he edge pq does no c oss an edge o T. Thus he ‘pocke ’ o med by π oge he wi h he edge pq and possible in e io edges and poin s is a ee polygon P. I δP pq is an x-mono onous pa h we a e done. O he wise we ma k he edge pq and apply induc ion on P. No e ha only one edge o Pis ma ked, since Tdoes no con ain cycles. Mo eo e , in e e y induc ion s ep we ob ain a smalle ins ance, since we ge id o a leas one edge o T.✷ Fo an edge ei s weigh is de ined as he numbe o poin s om Swhich lie in he open x-in e al spanned by e, ha is, he numbe o poin s which lie be ween he endpoin s o ein he x-so ed o - de . The weigh o a ee T, deno ed by w(T), is he sum o he weigh s o i s edges. Ob iously Tchas weigh ze o and is he only ee wi h his p ope y. Since each o he n−1 edges o Thas a mos weigh n−2 he weigh o a ee wi h n poin s is bounded by (n−1)(n−2) < n2. A igh bound is gi en by he ollowing lemma, o which we omi he p oo in his ex ended abs ac . Fig. 4. A ee wi h maximum weigh o 3n2−10n+8 4. Lemma 4 The weigh w(T)o a c ossing- ee spanning ee T∈ TSis bounded by 0≤w(T)≤ ⌊3n2−10n+8 4⌋,n≥2, and hese bounds a e igh . Lemma 5 Any c ossing- ee spanning ee T∈ TS can be ans o med in o Tcby a mos 2·w(T)edge slides. e p p’ e’ q π Fig. 5. A slide iangle (e, p) wi h x-mono onous pa h π connec ing p o q. P oo I T=Tc he s a emen is ob iously ue, so le T6=Tc. Le (e, p) be a slide iangle as p o- ided by Theo em 3, see Figu e 5. Le k≥1 be he numbe o edges o he x-mono onous pa h πcon- nec ing p o some endpoin qo e. We claim ha we can educe he weigh o eby a leas kby pe - o ming 2k−1 edge slides. To his end le e′be he edge o πinciden o q. Ou i s ask is o slide e′ along π o ob ain he edge qp. Assume ha k > 1. Then πa oids he in e io o he slide iangle (e, p) and hus con ains a leas one e ex p′poin ed away om he edge qp. Since πis x-mono onous we can slide he edge o πwhich has p′as i s le endpoin ‘ owa ds’ palong he edge o πwhich has p′as i s igh endpoin . We epea his p ocess un il we ob ain he edge qp, i.e., k= 1. Since each edge slide educes he leng h o he cu en pa h om p o qby one, we ca y ou exac ly k−1 s eps. Now we can slide ealong qp, educing i s weigh by a leas k( he e ices o πdi e en om q). Finally we slide qp back o e′by e e sing he s eps o he i s phase. 20 h Eu opean Wo kshop on Compu a ional Geome y As long as he esul ing ee is no Tcwe epea all abo e s eps. A e each i e a ion he weigh o a single edge has been dec eased by a leas hal o he numbe o he in ol ed edge slide ope a ions. We hus can ans o m Tin o Tcwi h a mos 2w(T) edge slides. ✷ We a e now eady o p o e ou main esul as p oposed in Sec ion 1. We gi e he e a mo e ex- plici s a emen and Theo em 1 hen ollows as a co olla y. Theo em 6 Fo any pai T′, T ′′ ∈ TSwe can ans o m T′in o T′′ by a mos 2(w(T′) + w(T′′)) ≤3n2edge slides. P oo Lemma 5 shows ha we can ans o m any ee T′∈ TSin o Tcwi h a mos 2w(T′) edge slides. By symme y o he edge slide ope a ion we can use he e e se ans o ma ion o T′′. To- ge he wi h he uppe bound w(T′), w(T′′ )≤3n2 4 om Lemma 4, he heo em ollows. ✷ p 1 p n−1 p n−4 p n−2 p n−3 p n Fig. 6. To ob ain he edge pnpn−2 equi es (n−1)(n−2)/2 edge slides o odd n≥3. Figu e 6 shows ha he e a e examples equi ing Ω(n2) edge slides o ans o m wo spanning ees in o each o he . Thus he bound o Theo em 1 is igh . We omi he de ails on he lowe bound con- s uc ion in his ex ended abs ac . 3. Discussion and Open P oblems One migh wonde whe he he slide-dis ance be ween wo spanning ees which do no in e sec each o he is smalle han in he gene al case. A simila esul holds o iangula ions, whe e he lip-dis ance can be bounded by he numbe o c ossing edges [4]. Howe e , om he example in Figu e 6 i ollows ha e en o wo ees di e ing in only one edge he slide-dis ance is quad a ic. Ano he obse a ion is ha he weigh o a spanning- ee is di ec ion-sensi i e. So an ob ious ques ion is whe he he e always exis s a ’nice’ di ec ion wi h sub-quad a ic weigh ? Again a neg- a i e answe is gi en by he example o Figu e 6, ha ing weigh Θ(n2) o any di ec ion o he x-axis. So a we only ob ained esul s on he numbe o necessa y slide ope a ions. On he algo i hmic side we a e also in e es ed in he ime complexi y o compu e he O(n2) slide sequence. We plan o in es iga e his ques ion in he nea u u e. A ela ed algo i hmic ques ion is how as we can compu e a di ec ion o minimize he weigh o a gi en ee. This can be done in ime O(n2log n), bu we omi he de ails in his ex ended abs ac . Acknowledgmen s We would like o hank Fe an Hu ado o his p esen a ion ‘Flip’ as he Paul E d¨os lec u e a CCCG 2003 in Hali ax, Canada. This inspi ed us o (con inue) wo k on he p esen ed opic. We a e g a e ul o F anz Au enhamme and Hannes K asse o enjoyable discussions and ca e ully eading he manusc ip . Re e ences [1] O.Aichholze , F.Au enhamme , F.Hu ado Sequences o spanning ees and a ixed ee heo em. Compu a ional Geome y: Theo y and Applica ions, 21(1-2):3–20, 2002. [2] D.A is, K.Fukuda Re e se sea ch o enume a ion. Disc e e Applied Ma hema ics 65: 618-632, 1996. [3] W.Godda d, H.C.Swa Dis ances be ween g aphs unde edge ope a ions. Disc e e Ma hema ics 161: 121–132, 1996. [4] S.Hanke, T.O mann, S.Schuie e The edge- lipping dis ance o iangula ions. Jou nal o Uni e sal Compu e Science 2 (1996), 570-579. [5] M.C.He nando, M.E.Houle, F.Hu ado On local ans o ma ion o polygons wi h isibili y p ope ies. P oc. 6 h In e na ional Compu ing and Combina o ics Con e ence COCOON’00, Sp inge LNCS 1858: 54–63, 2000.