Geome ic dila ion o closed plana cu es: A new lowe bound
Anne e Ebbe s-Baumann a, Ansga G ¨une a, and Rol Klein a
aDep . o Compu e Science I, Uni e si y o Bonn, D - 53117 Bonn, Ge many
Abs ac
Gi en any simple closed cu e Cin he Euclidean plane, le wand Ddeno e he minimal and he maximal
calipe dis ances o C, co espondingly. We show ha any such cu e Chas a geome ic dila ion o a leas
a csin( w
D) + p(w
D)2
−1.
Key wo ds: compu a ional geome y, con ex geome y, con ex cu es, dila ion, de ou , lowe bound
1. In oduc ion
Le Cbe a simple closed cu e Cin he Eu-
clidean plane. Fo any wo poin s, pand q, on C
le π(p, q) deno e he sho e o he wo cu e seg-
men s o C ha connec s pwi h q. Then he geo-
me ic dila ion, δ(C), o Cis de ined as
δ(C) := sup
p,q∈C,p6=q
|π(p, q)|
|pq|(1)
The compu a ion o he geome ic dila ion ( hen
called de ou ) was i s s udied in [5], whe e an
O(nlog n) app oxima ion algo i hm o polygonal
chains in he plane was gi en. Fu he e icien al-
go i hms o compu e he geome ic dila ion o ce -
ain classes o cu es and ne wo ks we e p esen ed
in [1], [11], and [9].
The ques ion o embedding a ini e poin se in
he plane in o a ne wo k wi h low geome ic dila-
ion was ecen ly s udied in [4]. The e i has been
shown ha any simple closed plana cu e has di-
la ion δ(C)≥π/2, using Cauchy’s su ace a ea
o mula.
No e, ha he analogue concep on g aphs,
whe e only he poin se o he e ices is aken
in o accoun o compu ing he dila ion, was ex-
ensi ely s udied unde he no ion o spanne s
and low dila ion g aphs, see e.g. [7] o a su ey
and [3], [2] o ecen esul s. Howe e , he e a e
Email add esses: ebbe [email protected] (Anne e
Ebbe s-Baumann), g [email protected] (Ansga
G ¨une), ol [email protected] (Rol Klein).
s uc u al di e ences be ween he wo concep s,
as al eady men ioned e.g. in [5].
In his pape we p o e a powe ul gene aliza ion
o he lowe bound om [4]. Namely, le wand D
deno e he wid h and he diame e o he con ex
hull o C, co espondingly, ha is, he minimal
and he maximal dis ances o a o a ing calipe
measu ing C; see Figu e 1.
C
D
w
Fig. 1. Diame e Dand wid h wo ch(C).
Then,
δ(C)≥a csin w
D+ w
D2−1 (2)
holds o he geome ic dila ion o C. This lowe
bound has a minimum alue o π/2 i and only i
w=Dholds. (No e, howe e , ha he ci cle is no
he only closed cu e sa is ying w=D.)
The p oo o o mula (2) uses a well-known ans-
o ma ion o con ex cu es called he cen al sym-
me iza ion, see e.g. [6] and [10].
The es o his pape is o ganized as ollows. In
Sec ion 2 we gi e some necessa y de ini ions and
20 h EWCG Se ille, Spain (2004)
20 h Eu opean Wo kshop on Compu a ional Geome y
basic lemma a. Then, in Sec ion 3 we ci e he sym-
me iza ion ans o ma ion. Finally, Sec ion 4 con-
ains he p oo o ou lowe bound.
2. De ini ions and basic p ope ies
Th oughou his pape we conside simple pla-
na cycles C, i.e. closed cu es in he Euclidean
plane wi hou sel -in e sec ions. A simple cycle C
is con ex i i always u ns in o he same di ec ion,
ha is, i Chas a con ex in e io domain.
De ini ion 1 (Dila ion) Le Cbe a simple cycle,
and le p, q ∈Cbe wo poin s on C.
(i) Cq
pdeno es one o he wo possible sub-pa hs
o Cconnec ing pand q, cha ac e ized by i s
u ning di ec ion: I one mo es om p o qon
Cq
p, one u ns an i-clockwise (C=Cq
p∪Cp
q).
(ii) The dila ion o a pai o poin s (p, q)∈
C×Cis he leng h o a sho es sub-pa h
πC(p, q)o Cconnec ing pand q,|πC(p, q)|=
min(Cq
p,Cp
q), di ided by i s Euclidean
dis ance, i.e. δC(p, q) := |πC(p,q)|
|pq|.
(iii) The geome ic dila ion o Cis he sup emum
o he dila ion alues o all pai s o poin s o
C, i.e. δ(C) := supp,q∈C,p6=qδC(p, q).
By con inui y and compac ness a gumen s one
can show ha e e y ini e con ex cu e has a pai
o poin s a aining maximum dila ion.
De ini ion 2 (Pa i ion Pai ) Le p∈Cbe a
poin on a cycle C. Then he unique pa i ion pa -
ne ˆpo pis cha ac e ized by |πC(p, ˆp)|=|C|/2.
We say ha (p, ˆp)is a pa i ion pai o C.
By con inui y a gumen s i is easy o show ha
o e e y di ec ion ∈S1 he e exis s a pa i ion
pai (p, ˆp), i.e. ˆp−p=|ˆp−p| .
De ini ion 3 (B ead hs) Le Cbe a simple cycle,
and le ∈S1be an a bi a y di ec ion.
(i) The -leng h o Cis he maximum dis ance o
a pai o poin s wi h di ec ion , i.e. lC( ) :=
max {|pq| | p, q ∈C, q −p=|q−p| }.
(ii) The -wid h ( -b ead h) o Cis he dis ance
o he wo suppo ing lines o Cpe pendicula
o , i.e. wC( ) := maxp∈Cp· −minp∈Cp· .
(iii) The -pa i ion pai dis ance,hC( ), o Cis
he dis ance o he pa i ion pai wi h di ec-
ion .
(i ) The diame e , D(C), o Cis he maximal
-leng h, i.e. D(C) := max ∈S1lC( ). The
wid h, w(C), o Cis he minimal -leng h,
i.e. w(C) := min ∈S1lC( ).
( ) The maximal pa i ion pai dis ance is de-
no ed by H(C) := max ∈S1hC( )and he
minimal pa i ion pai dis ance by h(C) :=
min ∈S1hC( ).
l( )
w( )
h( )
C
Fig. 2. Th ee di e en b ead h measu es.
As used in he in oduc ion, wid h and diame e
can also be de ined using he -wid h alues which
is p o ed in [8], [12] espec i ely:
Lemma 4 Le Cbe a simple cycle, hen D(C) =
max ∈S1wC( ). I Cis con ex, hen w(C) =
min ∈S1wC( ).
The nex s a emen ollows immedia ely om
he de ini ions; see Figu e 2.
Lemma 5 Le Cbe a simple con ex cycle, and le
∈S1be an a bi a y di ec ion. Then he ollowing
inequali ies hold: hC( )≤lC( )≤wC( ).
3. Cen al symme iza ion
The cen al symme iza ion (see e.g. [6], [8], [10])
is a well-known ans o ma ion which maps any
con ex cycle o a con ex poin -symme ic cycle.
In ou no ion, he cen al symme iza ion is based
on he leng h alues lC( ), in oduced in De ini-
ion 3(i).
Amazingly, i p ese es all he wid h alues
wC( ). And Cauchy’s su ace a ea o mula implies
ha he pe ime e is no changed ei he .
De ini ion 6 Le Cbe a con ex cycle. The cen al
symme iza ion o Cis he cycle C′gi en by he
pa ame iza ion c′:S1→R2,c′( ) := lC( )
2 .
As depic ed in Figu e 3, we can cons uc he
cen al symme iza ion by ansla ing all he cen-
e s o he segmen s o maximal leng h connec ing
pai s o poin s on C o he o igin.
Howe e , he e is an easie and mo e help ul con-
s uc ion, desc ibed in he ollowing lemma.
Ma ch 25-26, 2004 Se ille (Spain)
C
C’
Fig. 3. The cen al symme iza ion o an isosceles
igh -angled iangle.
Lemma 7 Le X:= (C)∪Cbe he ace bounded
by Cincluding Ci sel . Then de ine a se X′ o be
he a i hme ic mean o Xand −X; see [10]. I is
he Minkowski sum X⊕−Xscaled by 1/2. Then,
he cen al symme iza ion C′is he bounda y o
his a i hme ic mean X′:
X:= (C)∪C
X′:= 1
2(X⊕−X)) = 1
2(u− )
u, ∈X
⇒C′=∂X′
PROOF. The p oo ha his second way o con-
s uc ing C′is also co ec is s aigh o wa d.
Le ∈S1be an a bi a y di ec ion. De ine l:=
sup{c∈R>0|c ∈X′}. Then due o X′being
closed, l is an elemen o X′. And o k > l he
poin k is no in X′. Thus, l ∈∂X′.
I also ollows ha he e a e p, q ∈Xsuch ha
l = (1/2)(q−p). On he o he hand, he de ini ion
o lyields ha k > l implies he e a e no p, q ∈X
sa is ying k = (1/2)(q−p). Thus, l= (1/2)lC( ).
Hence, ou analysis esul s in he ollowing
pa ame iza ion o ∂X′:c′( ) = (1/2)lC( ) . And
his is exac ly he pa ame iza ion we used o
de ine C′.
The ollowing lemma, s a ed he e wi hou p oo ,
lis s he mos impo an p ope ies o he cen al
symme iza ion. The ac ha he wid h alues a e
p ese ed is men ioned wi hou p oo in [6]. G i z-
mann and Klee [8] p o e he wid h-p ese ing and
leng h-p ese ing p ope y. The s a emen ha
he pe ime e is p ese ed is also p o ed in [10].
Lemma 8 Le Cbe a simple con ex cycle, and le
C′be i s cen al symme iza ion. Then, he cycle
C′has he ollowing p ope ies:
(i) Cycle C′is con ex.
(ii) Cycle C′is poin -symme ic wi h espec o
he o igin.
(iii) Fo e e y di ec ion ∈S1,hC′( ) = lC′( ) =
lC( )≥hC( ), and wC′( ) = wC( ).
(i ) Wid h, diame e and pe ime e a e p ese ed
by cen al symme iza ion, i.e. w(C′) =
w(C),D(C′) = D(C)and |C′|=|C|.
Because we can show ha he dila ion o a con-
ex cycle is always a ained by a pa i ion pai , i
ollows easily om hose p ope ies ha he dila-
ion o he ans o med cycle canno be la ge hen
he o iginal one:
Lemma 9 The dila ion o C′is no la ge han he
o iginal dila ion, i.e. δ(C′)≤δ(C).
4. The lowe bound
To apply he ans o ma ion desc ibed in Sec-
ion 3, we need he ac ha he dila ion o he
bounda y o he con ex hull o any plana cycle
Cis a mos he dila ion o Ci sel . Due o space
limi a ions we s a e his he e wi hou p oo .
Theo em 10 Le C⊂
R
2be a simple closed
cu e. Le ∂ch(C)deno e he bounda y o he con-
ex hull o C. Then holds
δ(C)≥δ(∂ch(C)).
Now we p o e ou esul on he lowe bound,
using he cen al symme iza ion ans o ma ion.
Theo em 11 Le C⊂
R
2be a simple closed
cu e. Le wbe he wid h and le Dbe he diame e
o ch(C), he con ex hull o C. Then he dila ion
o Cis bounded om below by
δ(C)≥a csin w
D+sD
w2
−1.
q
c
R
α
x
p
B (c)
Fig. 4. The sho es cycle no in e sec ing he disk B (c).
PROOF. Because o Theo em 10 we can assume
w.l.o.g. ha Cis con ex. To show he main idea
o he p oo we i s conside a poin -symme ic
cycle ˜
C⊂
R
2wi h cen e -poin c, see Figu e 4.
Then, ob iously, he pa i ion pai s a e also poin -
symme ic wi h espec o c. Le (p, q) be a pa i-
20 h Eu opean Wo kshop on Compu a ional Geome y
ion pai ha ing maximum dis ance |pq|=H(˜
C).
We de ine R:= H(˜
C)/2.
Le B (c) be he open disc wi h cen e poin c
and adius := h(˜
C)/2, ha is B (c) := {b∈
R
2||b−c|< }. Then ˜
Ccanno in e sec wi h
B (c), o he wise he e would exis a pa i ion pai
ha ing a dis ance smalle han h(˜
C) = 2 .
By using he sho es possible cyclic pa h con-
nec ing pand qin he Euclidean plane, no in e -
sec ing B (c) bu enclosing i , we ob ain a cu e
˜
CminP e , as shown in Figu e 4. By cons uc ion
˜
CminP e is he poin -symme ic cu e o smalles
pe ime e ha has minimum pa i ion pai dis-
ance h(˜
C) and maximum pa i ion pai dis ance
H(˜
C). Due o symme y easons his pe ime e is
P= 4x+ 4 α, wi h xdeno ing he leng hs o he
s aigh pa h segmen s om pand q o he an-
gen poin s on B (c), co espondingly, and α he
leng hs o he pa h segmen s on ∂B (c).
Using Py hago as we ge x=√R2− 2. And by
conside ing he angles in he ec angula iangle,
we ob ain sin α= cos(π
2−α) =
R. Because he
maximum dila ion o he con ex cycle ˜
Cis a ained
by a pa i ion pai ha ing sho es pa h dis ance
˜
P
2≥P
2, i holds:
δ(˜
C)≥
P
2
2 =4x+ 4 α
4 =√R2− 2
+ a csin 
R
=sR
2
−1 + a csin 
R(3)
Now, le Cbe an a bi a y con ex cycle, and le
C′be i s cen al symme iza ion. Then, Lemma 9
yields ha δ(C)≥δ(C′). And by Lemma 8(i )
we know ha wid h and diame e a e p ese ed,
i.e. w(C′) = w(C) and D(C′) = D(C). Howe e ,
in a poin -symme ic con ex cycle -leng h and -
pa i ion pai dis ance a e equal, implying w(C′) =
h(C′) and D(C′) = H(C′).
Thus, i we apply o mula (3) o C′keeping in
mind ha =h(C′)/2 = w(C′)/2 = w(C)/2 =
w/2 and R=H(C′)/2 = D(C′)/2 = D(C)/2 =
D/2, we ge :
δ(C)≥sD
w2
−1 + a csin w
D
This lowe bound equals he global lowe bound
o π
2shown in [4] only o cu es o cons an wid h
(w=D). Fu he a gumen s show ha he in-
equali y ge s s ic i Cis no poin -symme ic o
no con ex. Hence, only ci cles ha e dila ion π
2.
Rema k 12 By eplacing lC( )by hC( )in De i-
ni ion 3 we ge a new ans o ma ion, he pa i ion
pai ans o ma ion. Ideas analogous o he ones
p esen ed he e show ha
δ(C)≥sH
h2
−1 + a csin h
H
whe e H=H(ch(C)) and h=h(ch(C)) o e e y
simple cycle C.
Re e ences
[1] P. Aga wal, R. Klein, Ch. Knaue , and M. Sha i .
Compu ing he de ou o polygonal cu es. Tech.
Repo B 02-03, FU Be lin, 2002.
[2] P. Bose, J. Gudmundsson, and M. Smid. Cons uc ing
plane spanne s o bounded deg ee and low weigh . In
P oc. 10 h Eu op. Symp. Algo., LNCS 2461:234–246,
2002.
[3] D.Z. Chen, G. Das, and M. Smid. Lowe bounds
o compu ing geome ic spanne s and app oxima e
sho es pa hs. Disc . Appl. Ma h., 110:151–167, 2001.
[4] A. Ebbe s-Baumann, A. G ¨une, and R. Klein. On he
geome ic dila ion o ini e poin se s. In P oc. 14 h
In e na . Symp. Algo. and Compu ., LNCS 2906:250–
259, 2003.
[5] A. Ebbe s-Baumann, R. Klein, E. Lange epe, and
A. Lingas. A as algo i hm o app oxima ing he
de ou o a polygonal chain. In P oc. 9 h Eu op. Symp.
Algo., LNCS 2161:321–332, 2001.
[6] H.G. Eggles on. Con exi y, Camb idge Uni e si y
P ess, 1958.
[7] D. Epps ein. Spanning ees and spanne s. In J.-R. Sack
and J. U u ia, edi o s, Handbook o Compu a ional
Geome y, pp. 425–461. Else ie , 1999.
[8] P. G i zmann and V. Klee. Inne and ou e j- adii
o con ex bodies in ini e-dimensional no med spaces.
Disc e e Compu . Geom., 7:255–280, 1992.
[9] Ansga G ¨une, Rol Klein, and Elma Lange epe.
Compu ing he de ou o polygons. In Abs ac s 19 h
Eu opean Wo kshop Compu . Geom., pages 61–64.
Uni e si y o Bonn, 2003.
[10] I.M. Jaglom and W.G. Bol janski. Kon exe Figu en,
VEB Deu sche Ve lag de Wissenscha en, 1956.
[11] S. Lange man, P. Mo in, and M. Soss. Compu ing he
maximum de ou and spanning a io o plana chains,
ees and cycles. In P oc. 19 h In e na . Symp. Theo .
Aspec s o C.Sc., LNCS 2285:250–261, 2002.
[12] S.R. Lay. Con ex Se s and hei Applica ions, John
Wiley & Sons, 1982.