Mo e esul s abou spanne s in he l1-me ic.∗
J. C´ace es†
, C. I. G ima, A. M´a quez‡and A. Mo eno-Gonz´alez§
Abs ac
In his wo k we s udy mo e ques ions abou spanne s in he l1-me ic. Conc e ely, we
will see ha adding some S eine poin s o a se o si es he me ically comple e g aph o
he new se has a linea numbe o edges. We will also cha ac e ize he ee dila ion ees.
Finally, inspi ed in he wo k o he l1-me ic, we will s udy poin s in gene al posi ion o
o he me ics, he λ-me ics.
1 In oduc ion.
The e a e many applica ions in geome ic ne wo k design in which i would be in e es ing o ind
g aphs wi h ew edges ha app oxima e sho es pa hs be ween all pai o e ices. Since in many
p oblems, as he design o VLSI ci cui s, he me ic ha e lexes he ac ual dis ance be ween
he e ices is he l1-me ic, in p e ious wo ks [2, 3] we p esen ed some esul s abou he i s
ques ions ha a ise in he s udy o hese g aphs. Gi en a se o si es Sin he plane, he dila ion o
a subg aph o he comple e geome ic g aph is he la ges a io be ween he leng h o he sho es
pa h om a pai o poin s o S o he dis ance o hose poin s in he plane. In his way, we ha e
p esen ed he nex esul s:
•I is possible o cons uc g aphs app oxima ing he comple e Euclidean g aph closely in
he l1-me ic. Mo eo e , we ound g aphs ha a e no he comple e g aph bu hey ha e
dila ion 1 (dila ion ee g aphs). Mo e p ecisely, gi en a se o si es Sin he plane, we call
he me ically comple e g aph o S(deno ed M(S)) o he minimal dila ion ee g aph.
•The me ically comple e g aph is s ic ly smalle han he comple e g aph in he l1-me ic;
in ac , i K(S) deno es he comple e geome ic g aph on S, hen |K(S)−M(S)| ∈ O(N3/2).
•The e exis s a cha ac e iza ion o he se o si es wi h a plana me ically comple e g aph.
Also, we ha e ound some necessa y condi ions o a plana g aph in o de o be isomo phic
o a me ically comple e g aph.
In his wo k we p esen some addi ional esul s ha con inue hose wo men ioned wo ks.
Fi s ly, gi en a se o si es Sin he plane we y o educe he size o M(S) and we will see ha
adding some S eine poin s o S he me ically comple e g aph o he new se o si es has a linea
numbe o edges. Secondly, we y o ind which ees ha e dila ion 1 in he l1-me ic, ob aining a
cha ac e iza ion o hese g aphs. Finally, we y o gene alize some o ou i s esul s o o he
me ics, he λ-me ics. In ac , we will see ha he me ically comple e g aph o a se o si es is
smalle han he comple e Euclidean g aph o hose me ics.
∗Pa ially suppo ed by MCyT p ojec BFM2001-2474
†Depa amen o de Ma em´a ica Aplicada y Es ad´ıs ica. Uni e sidad de Alme ´ıa. E-mail: [email p o ec ed]
‡Depa amen o de Ma em´a ica Aplicada I. Uni e sidad de Se illa. E-mail: {g ima,alma }@us.es
§Depa amen o de Ma em´a icas. Uni e sidad de Huel a. E-mail: [email p o ec ed]
65
2 I is possible o educe he size o a me ically comple e
g aph.
As we ha e said abo e, gi en a se o si es Sin he plane, |K(S)−M(S)| ∈ O(N3/2) in he
l1-me ic, bu , in gene al, M(S) has a quad a ic numbe o edges. Thus, he i s ques ion we
conside is o educe he size o M(S) adding some new poin s o S. In o de o ind hese poin s
we only ha e o make a pa i ion o he ini ial se o si es ha leads o a kd- ee [1], (see Figu e 1).
Then, we add one S eine poin in he in e sec ions o he lines used o make he pa i ion. Then,
we can p o e he nex esul .
p
p
p
p
p
p
p
p
p
p
1
2
3
4
5
6
7
8
9
10
l
l
l
l
l
l
l
l
2
3
4
5
6
7
8
9
l
1
Figu e 1: A pa i ion o a se o si es.
Theo em 1 Gi en a se o nsi es Sin he plane, he e exis s a linea numbe o S eine poin s
S e i ying ha |M(S∪S )| ∈ O(n).
3 F ee dila ion ees.
As we ha e said in he In oduc ion, he second ques ion we y o sol e is o ind which a e he
ees wi h dila ion 1. In he Euclidean me ic he answe o his ques ion is e y simple: we can
only cons uc a ee dila ion ee when he si es a e in a s aigh line. In he l1-me ic, some new
cases appea .
Theo em 2 I Tis a ee dila ion ee, hen Tis isomo phic o one o he ees in Figu e 2.
4 Poin s in gene al posi ion o a λ-me ic.
Gi en a λ-me ic, a ball cen e ed in xand adio is a egula polygon o λedges e i ying ha
he Euclidean dis ance be ween xand he e ices o he polygon is .
Obse e ha o any alue o λ he e exis in ini e egula polygons cen e ed in x, so a λ-me ic
is no only cha ac e ized by he numbe o edges, bu also by hei o ien a ion. Howe e , i is only
necessa y o sol e he ques ion o one o hem.
One o he 4-me ics is he l1-me ic, so i is na u al o conside he ques ion o cons uc ing
ee dila ion g aphs o o he alues o λ. In ac , we will see ha he me ically comple e g aph
o a se o poin s has less edges ha he comple e g aph in a λ-me ic. In o de o sol e his esul
66
(a) (b)
(c) (d)
Figu e 2: F ee dila ion ees in he l1-me ic.
we will p o e ha o e e y λ, he e exis s a numbe n(λ) e i ying ha any se o poin s wi h
mo e han n(λ) poin s in gene al posi ion o he Euclidean me ic, is no in gene al posi ion in he
λ-me ic. We conside ha a se o poin s is in gene al posi ion i he e a e no h ee consecu i e
poin s in a s aigh line.
Then, he i s ques ion we mus sol e is o ind he minimum a c be ween wo poin s. Then,
le u1, u2be wo poin s in he plane and o each poin uiwe conside a neighbo Ei. These
neighbo s make a pa i ion o he plane in sec o s cen e ed in he ini ial poin s. I we call Sij he
sec o cen e ed in ui ha con ains uj, he minimum a cs be ween uiand uja e all he a cs no
dec easing pa allel o he bo de o Sij TSji, [7, 5], (see Figu e 3).
u
Figu e 3: Two minimum a cs be ween uiand ujin a 6-me ic.
Lemma 1 Gi en a λ-me ic, he e exis , a mos , λpoin s in con ex posi ion in gene al posi ion.
Now, in 1935 E d¨os y Szeke es [4] p o ed ha o e e y na u al numbe n he e exis s an in ege
g(n) e i ying ha o e e y se wi h mo e han g(n) poin s, he e a e nin con ex posi ion. Then,
we can p o e he nex esul .
67
Theo em 3 Fo any alue o λ he e exis s n(λ) e i ying ha e e y se o poin s wi h, a leas ,
n(λ)poin s is no in gene al posi ion.
Now, ou objec i e is o ind bounds o n(λ). I is ob ious ha
λ+ 1 ≤n(λ)≤g(λ+ 1),
and i is known [6] ha
g(n)≤µ2n−5
n−2¶+ 2
Howe e , his bound does no seem o be igh because o n= 4 we ob ain 12 as uppe bound
and we know ha n(4) = 5. In ac , o small alues o λ, i is easy o p o e ha n(λ) = λ+ 1.
Re e ences
[1] J. L. Ben ley. Mul idimensional bina y sea ch ees used o associa i e sea ching. Commun.
ACM, 18:509–517. 1975.
[2] J. C´ace es, C. I. G ima, A. M´a quez and A. Mo eno-Gonz´alez. Dila ion ee g aphs in l1-me ic.
17 h Eu opean Wo kshop on Compu a ional Geome y, Be lin. 2001.
[3] J. C´ace es, C. I. G ima, A. M´a quez and A. Mo eno-Gonz´alez. Plana g aphs and me ically
comple e g aphs. 18 h Eu opean Wo kshop on Compu a ional Geome y, Wa saw. 2002.
[4] P. E d¨os and G. Szeke es. A combina o ial p oblem in geome y. em Composi io Ma h.,
2:463–470. 1935.
[5] R. Klein. Conc e e and Abs ac Vo onoi Diag ams. Lec u e No es in Compu e Science.
Sp inge -Ve lag. 1989.
[6] G. To h and P.Val . No e on he E d¨os-Szeke es heo em. Ru ge Uni e si y. Technical Repo
DIMACS TR:97-31. 1997.
[7] P. Widmaye , Y. F. Yu and C. K. Wong. Dis ance p oblems in compu a ional geome y o
ixed o ien a ions. P oceedings 1s ACM Symposium on Compu a ional Geome y, 186–195.
1985.
68