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.