Spanners in l1
Full text
99Session C3.2 12 h Canadian Con e ence on Compu a ional Geome y
Spanne s in l
1
J. Ca c e e s
1
, C. I . G i m a
2
, A . M a q u e z
2
an d A. M o e n o - G o n z a l e z
2
[1] Depa amen o de Es ads ica y Ma ema ica Aplicada,
Uni e sidad de Alme a (Spain).
jcace [email protected]
[2] Depa amen o de Ma ema ica Aplicada I, Uni e sidad de
Se illa (Spain).
[email p o ec ed]s, alma @cica.es, amo eno@eule . ie.us.es
Abs ac
In his wo k, h ee p oblems a ising in geome ic ne -
wo k design heo y a e conside ed using he
l
1
me ic.
We s s udy he alues o
o which he
-Yao g aph
(using he me ic ab o e) con ains he
M S T
o a collec-
ion o si es in he plane, and addi ionally, we conside
he same p oblem wi h o he
l
p
me ics. Secondly, we
gi e upp e b ounds o he dila ion o
-Yao in he
l
1
me ic. And nally, we s udy he size o a g aph wi h
dila ion 1 in he
l
1
me ic.
Key wo ds:
Spanne , MST, dila ion, comple e geo-
me ic g aph, Minkowski me ics.
1 In o duc ion
The quali y o a ne wo k in e connec ing p oin s can b e
measu ed in die en ways. Typically some minimal
condi ions a e imp osed o he ne wo k; o ins ance,
i is usually desi ed ha he Minimum Spanning T ee
(MST) mus b e con ained in he ne wo k. Bu when
one ies o design a go o d ne wo k o connec ing com-
p onen s o a VLSI ci cui such ha uses li le su ace
a ea on he chip, d aws li le p owe and p opaga es
signals quickly, i could b e in e es ing o nd a spa se
g aph which app oxima es sho es pa hs b e ween all
pai s o e ices. Those g aphs a e called
spanne s
and
hey ha e b een ex ensi ely s udied [1] [2] [3] [4] [7].
Mo e p ecisely, gi en a se o p oin s
S
in he plane, he
dila ion
o a subg aph o he comple e geome ic g aph
is he la ges a io b e ween he leng h o he sho es
pa h om a pai o p oin s o
S
o he dis ance o hose
p oin s in he plane. A g aph wi h dila ion
is called a
( )-spanne
o
S
. Bu , al hough he me ic ha eexes
he dis ance b e ween comp onen s in an elec onic ci -
cui is he
l
1
me ic, all ci ed wo ks a e o cused on he
Euclidean me ic. We y, in his wo k, o s udy some
o he s ques ions ha a ise in he s udy o spanne s
bu wi h he
l
1
me ic (ob aining some esul s o he
l
1
me ic as well). Remind ha he
l
1
and
l
1
me -
ics a e he Manha an and he Sup eme me ics, e-
sp ec i ely; ha is, gi en wo p oin s
A
= (
a
1
; a
2
)
; B
=
(
b
1
; b
2
)
2
R
2
,
d
l
1
(
A; B
) =
j
b
1
?
a
1
j
+
j
b
2
?
a
2
j
and
d
l
1
(
A; B
) =
max
j
b
1
?
a
1
j
;
j
b
2
?
a
2
jg
.
I is p ossible o nd spa se g aphs app oxima ing
he comple e Euclidean g aph a bi a y closely. Thus,
Keil [6] showed ha a class o g aphs called Yao g aphs
p o duces g aphs wi h dila ion a bi a y closed o 1,
wi h
O
(
n
) edges and ha hey can b e cons uc ed in
ime
O
(
n
log
n
). Thus, he s ques ion, ea ed in
he nex sec ion, will b e o s udy whe he a Yao g aph
con ains he MST in b o h he
l
1
o he
l
1
me ics. Sec-
ondly, we will s udy he dila ion o hose g aphs. And,
nally, we will see ha in he
l
1
me ic g aphs wi h
dila ion 1 ha e much less edges ha in he Euclidean
dis ance.
2
- Yao g aphs and MST o a
collec ion o si es in he
l
1
me -
ic.
As i was p oin ed ou in he In o duc ion, in his sec ion
we s udy which a e he Yao g aphs ha con ain he
MST o a collec ion o si es in he me ic
l
1
. Fi s o all,
we will gi e he
-Yao g aph cons uc ion in any me ic.
Le
S
b e a collec ion o si es in
R
2
. We pa i ion he
space a ound each p oin in o wedges wi h a gi en xed
op ening angle,
, and connec he p oin o he nea es
neighb o in each wedge wi h he gi en me ic. The
g aph ob ained is called he
-Yao g aph o
S
.
In his wo k, we ex end his deni ion and we will
call (
;
)-Yao g aph o he
-Yao g aph cons uc ed by
placing he b o de s o he s wedge o ming an angle
wi h he abscissae axis, as we can see in Figu e 1.
u
Figu e 1: Cons uc ion o a (
;
)-Yao g aph.
Wi h his new concep we wan o know he alues
o
and
o which he (
;
)-Yao g aph con ains he
MST o a collec ion o si es. This p oblem was s udied
by Yao [8] o he Euclidean me ic and he p o ed ha
any
=
3-Yao g aph o a se o si es con ains he MST
o he si es. In his wo k we gi e simila esul s o he
100 CCCG 2000, F ede ic on, New B unswick Session C3.2
me ics
l
1
and
l
1
.
Theo em 1
Le
S
be a se o si es in
R
2
. Any
(
; =
4)
-Yao g aph o
S
con ains he MST o he si es
in he
l
1
me ic.
P oo :
Wi hou loss o gene ali y, we can supp ose ha
2
[0
; =
4).
We know ha he MST o a se o si es
S
can b e
buil inc emen ally by adding he sho es edge joining
S
1
and
S
2
no explo ed ye , which also main ains he
acyclici y, (whe e
S
1
is he subse o si es ha ha e
al eady b een aken and
S
2
=
S
?
S
1
).
Supp ose hen ha in a s ep o his algo i hm, we
ha e o ake he edge
uw ; u
2
S
1
; w
2
S
2
and ha his
edge is no an edge o he (
; =
4)-Yao g aph o
S
wi h
he
l
1
me ic. In his case, i we place he wedges in
u
,
he e is an edge
u
, sho e han
uw
, ha ha e b een
selec ed b e o e.
Then, we only ha e o p o e ha
d
(
u; w
)
d
(
w ;
)
in he
l
1
me ic. The wo s case o ccu s when
u
and
uw
a e simila in leng h bu widely sepa a ed in angle,
as we see in Figu e 2.
u
wa
a
b
c
Figu e 2: The wo s case o he p o o o
d
(
u; w
)
d
(
w ;
), (see ex ).
In Figu e 2 we can also see ha
an
=
b
a
+
c
;
an(
+
=
4) =
a
+
b
c
:
Bu , by o he side we ha e ha
an(
+
=
4) =
sin(
+
=
4)
cos(
+
=
4)
=
1 + an
1
?
an
:
So, we ge
a
+
b
c
=
1 +
b
a
+
c
1
?
b
a
+
c
;
and, simpli ying we ha e
a
2
=
b
2
+
c
2
. Now, i is easy
o see ha
a
b
+
c
, so he esul holds.
2
The b ound ob ained in Theo em 1 is igh , and so
gi en
> =
4 i is p ossible o nd a
-Yao g aph o a
se o si es ha do es no con ain he MST.
Theo em 2
Le
S
be a se o si es in
R
2
. The
(
=
4
; =
2)
-Yao g aph o
S
con ains he MST o he si es
in he
l
1
me ic, bu he e exis s col lec ions o si es
S
such he
(0
; =
2)
-Yao g aph does no con ain he MST
o
S
in ha me ic.
P oo :
Fi s ly, we p o e ha he (
=
4
; =
2)-Yao g aph
con ains he MST o any se o si es. The p o o is
simila o ha o Theo em 1, so we only ha e o p o e
ha he edge
w
is sho e han
uw
in he
l
1
me ic,
b eing
w
a si e in he wedge whe e
is, (see Figu e 3).
u
Figu e 3:
w
is a si e in he colo ed egion.
Bu , as we can see in Figu e 3, any si e in he b o de
o he disc wi h cen e
u
and adio
d
(
u;
) is a he
same dis ance om
u
han om
. So, i is i ial o
see ha he dis ance b e ween
w
and
u
is no smalle
han he dis ance b e ween
w
and
. So, he (
=
4
; =
2)-
Yao g aph con ains he MST o any se o si es.
Now, we gi e an example o a collec ion o si es
S
such he (0
; =
2)-Yao g aph do es no con ain he MST
o
S
in he
l
1
me ic. We conside he se
S
=
x
=
(0
;
0)
; y
= (1
0
25
;
?
0
0
25)
; z
= (2
;
1)
; u
= (0
0
5
;
1
0
5)
;
=
(1
;
1
0
25). Then, in Figu e 4 we see ha he (0
; =
2)-
Yao g aph do es no con ain he MST o
S
.
xy
z
u
xy
z
u
Yao g aph MST
Figu e 4:
y
is an edge o he MST o
S
bu i is no
an edge o he (0
; =
2)-Yao g aph o
S
.
2
101Session C3.2 12 h Canadian Con e ence on Compu a ional Geome y
Ou nex s ep is o s udy he same p oblem o he
l
1
me ic. Fi s ly, we conside he p oblem o nding
an angle
ha sa ises ha any (
;
)-Yao g aph o
a se o si es con ains he MST o he si es. He e, he
esul is simila o ha gi en o he
l
1
me ic.
Theo em 3
Le
S
be a se o si es in
R
2
. Any
(
; =
4)
-Yao g aph o
S
con ains he MST o he si es
in he
l
1
me ic.
P oo :
The p o o o his esul is simila o hose o
Theo ems 1 and 2. As in Theo em 1, we only p o e he
esul o
2
[0
; =
4). We ha e o p o e ha he edge
uw
is longe han
w
wi h he
l
1
me ic, (see Figu e 5).
u
w
a
a
b
c
Figu e 5:
uw
is no sho e han
w
.
Bu , as we can see in Figu e 5, i is i ial ha
b; c <
a
, so he esul holds.
2
Secondly, we s udy wha happ ens o he
=
2-Yao
g aphs o a collec ion o si es and we see ha he si u-
a ion is comple ely die en .
Theo em 4
Le
S
be a se o si es in
R
2
. The
(0
; =
2)
-Yao g aph o
S
con ains he MST o he si es
in he
l
1
me ic, bu he e exis s col lec ions o si es
S
such he
(
=
4
; =
2)
-Yao g aph does no con ain he
MST o
S
in ha me ic.
P oo :
Fi s ly, we p o e ha he (0
; =
2)-Yao g aph o
aany se o si es
S
con ains i s MST. The p o o o his
esul is simila o ha o Theo em 3, so we only ha e
o p o e ha he edge
uw
is no sho e han he edge
w
in he
l
1
me ic, whe e
w
is a si e in he wedge
whe e
is, (see Figu e 6).
Bu , i is easy o see ha any si e in he b o de o
he disc wi h cen e
and adio
d
(
u;
) is nea e o
han o
u
, so he esul holds.
Now, we gi e an example o a collec ion o si es
S
such he (
=
4
; =
2)-Yao g aph do es no con ain
u
Figu e 6:
w
lies in he colo ed egion.
he MST o
S
in he
l
1
me ic. We conside he
se
S
=
x
= (0
;
0)
; y
= (1
0
5
;
1)
; z
= (1
;
3)
; u
=
(
?
0
0
25
;
2
0
25)
;
= (
?
1
;
2). Then, in Figu e 7 we see
ha he (
=
4
; =
2)-Yao g aph do es no con ain he
MST o
S
.
x
y
z
u
Yao g aph MST
x
y
z
u
Figu e 7:
uy
is an edge o he MST o
S
bu i is no
an edge o he (
=
4
; =
2)-Yao g aph o
S
.
2
3 Dila ion in
-Yao g aphs.
In his sec ion we s udy he dila ion in he (
;
)-Yao
g aphs o a collec ion o si es. As we did in he p e ious
sec ion, we gi e a simila esul o one gi en by Keil [6]
o he Euclidean me ic. In his way, we ha e ound
upp e b ounds o he dila ion in he (
;
)-Yao g aphs
o a se o si es in he
l
1
me ic.
Theo em 5
Le
S
be a se o si es in
R
2
. The
(
;
)
-
Yao g aph o he si es has dila ion a bi a y closed o 1
when
ends o 0.
P oo :
To nd a pa h in his g aph om
u
o
, one a
each s ep de e mines he wedge con aining
and mo es
along a g aph edge o he nea es e ex,
w
, in ha
102 CCCG 2000, F ede ic on, New B unswick Session C3.2
wedge. The wo s case o he algo i hm o ccu s when
u
and
uw
a e simila in leng h bu widely sepa a ed
in angle, as we see in Figu e 8, bu wi h p op e ies
o angles and iangles we can b ound he dila ion, as
ollows.
u
w
a
a
h
l
l1
2
Figu e 8: The wo s case o he dila ion.
We deno e by
d
(
;
)
(
S
) he dila ion o he (
;
)-Yao
g aph o he se
S
. We know ha
d
(
;
)
(
S
) =
j
u
j
+
j
w
j
j
uw
j
:
Bu , as we can see in Figu e 8,
j
u
j
=
j
uw
j
=
a
+
l
1
+
l
2
and
j
w
j
= 2
a
, so we ha e ha
d
(
;
)
(
S
) = 1 +
2
a
l
1
+
l
2
+
a
:
On he o he hand, we ha e
sin
h
=
sin(
?
=
4
?
?
)
d
e
(
u;
)
sin(
?
=
4
?
?
)
j
u
j
:
So, as
a
h
, we ge ha
d
(
;
)
(
S
)
1 + 2
sin
sin(
?
=
4
?
?
)
;
ha ends o 1 when
ends o 0.
2
Wi h his esul , we p o ide a way o cons uc span-
ne s wi h dila ion as closed o 1 as we wan .
4 G aphs wi h dila ion 1 in he
l
1
me ic.
As we men ioned in he In o duc ion, in his sec ion
we see ha in he
l
1
me ic g aphs wi h dila ion 1 ha e
much less edges ha in he Euclidean dis ance. We also
gi e h ee die en algo i hms o cons uc ing hese
g aphs.
Le
S
b e a se o
n
si es in
R
2
. We deno e by
M
n
a g aph o minimal size o
S
wi h dila ion 1. In he
Euclidean me ic, excep i he si es a e on a s aigh
line,
M
n
is he comple e geome ic g aph o he si es
K
n
. Tha is,
M
n
has
n
(
n
?
1)
2
edges.
Wi h he
l
1
me ic his esul can b e imp o ed by
i ue o a esul by E dos and Szeke es [5]: In any
sequence o
pq
+ 1 in ege s, he e exis s an inc easing
subsequence o leng h
p
o a dec easing subsequence o
leng h
q
.
We o de he si es by hei s co o dina es and hen,
we can use he esul by E dos and Szeke es aking
he second co o dina es as a sequence, ob aining h ee
die en cases:
I (
b
n
c
+ 1)
b
n
c
+ 1
n
, hen he e exis an inc eas-
ing subsequence o leng h
b
n
c
+ 1 and a dec easing
subsequence o he same leng h.
I
b
n
cb
n
c
+ 1
n
, hen he e exis s a dec easing
o inc easing subsequence o leng h
b
n
c
+ 1.
In o he case, he e exis s a dec easing subsequence
o leng h
b
n
c
and an inc easing subsequence o he
same leng h.
In hese cases, all he edges ha o m he comple e
geome ic g aph o he subsequences a e no needed in
M
n
, excep he ones ha join he co ela i e si es. In
Figu e 9 we can see an example wi h 7 si es, whe e we
ha e wo subsequences o leng h 3. The edges ha we
sa e in each subsequence a e ma ked.
(a) (b)
Figu e 9: (a) Two subsequences o leng h 3; (b) edges
sa ed in each subsequence.
Now, we can use he esul again wi h he si es ha
ha e no b een aken in he dec easing o inc easing sub-
sequences, so we ob ain die en subsequences o die -
en size in which we can e ase edges. We can e en ake
a si e in each subsequence and use he esul by E dos
and Szeke es again.
Then, wi h his me ho d, we ha e a way o app oxi-
ma e he numb e o edges o
K
n
?
M
n
. In ac we ha e
go a unc ion ha p o duces his numb e and we ha e
103Session C3.2 12 h Canadian Con e ence on Compu a ional Geome y
compa ed i wi h o he unc ions ob aining ha ha
unc ion is in
O
(
n
3
=
2
).
Now, we p esen a esul in which we gi e an upp e
b ound o he size o
K
n
?
M
n
.
Theo em 6
Le
S
be a col lec ion o
n
si es in
R
2
.
Wi h he
l
1
me ic,
j
K
n
?
M
n
j 2
O
(
n
3
=
2
)
.
P oo :
Le
S
b e a se o si es in
R
2
and le
L
1
: : : L
k
i s con ex laye s. In any o hese laye s we ha e ou
die en dec easing o inc easing chains o si es, (see
Figu e 10).
C
CCC
CC
1
2
34
Figu e 10: An example o he ou chains in a con ex
laye .
In Figu e 10 we can also see ha in each chain we
only need he edges joining co ela i e si es, ha is, in
each chain
C
i
we do no use
j
C
i
j
(
j
C
i
j ?
1)
2
?
(
j
C
i
j ?
1)
edges.
Gi en any con ex laye
L
i
, he wo s case is when we
ha e
j
L
i
j
=
4 si es in each chain. In his case, we do no
use
j
L
i
j
4
(
j
L
i
j
4
?
1)
2
?
(
j
L
i
j
4
?
1)
edges in each chain, so he numb e o edges no needed
in a lawye is ou imes he p e ious one.
Then, as we ha e
k
con ex laye s, i is i ial o see
ha he o al numb e o edges ha we do no use is
k
X
i
=1
j
L
i
j
4
(
j
L
i
j
4
?
1)
2
?
(
j
L
i
j
4
?
1)
:
Now, i we s udy he p e ious exp ession, we see ha
he wo s case is when
k
=
p
n
and he e a e
p
n
si es
in each laye . So, we ge ha a leas
p
n
(
n
8
?
3
p
n
2
+ 4)
edges a e no needed in
M
n
.
On he o he side, we can conside a si e in he las
con ex laye and hen pa i ion he space a ound his
p oin in o ou wedges wi h b o de s pa allel o he axis.
Then, we do no need he edges joining si es in he
s wedge and he hi d one and edges joining si es
in he second wedges and he ou h one. This hap-
p ens b ecause we ha e a pa h b e ween hese si es, (see
Figu e 11).
u
w
z
Figu e 11: We do no need he edges
u
and
w z
.
Now, in he las con ex laye he e a e
p
n
si es and
i we s udy he p osi ion o he es o si es we ob ain
ha he wo s case is when we ha e
p
n=
2 si es in he
s and second wedges and (
n
?
2
p
n
)
=
2 in he hi d
and ou h wedges. So, we sa e 2
p
n
2
(
n
?
2
p
n
2
) edges.
In conclusion,
j
K
n
?
M
n
j
has a leas
5
8
n
p
n
?
5
2
n
+
4
p
n
edges, so
j
K
n
?
M
n
j 2
O
(
n
3
=
2
).
2
Co olla y 7
Le
S
be a se o si es in
R
2
. Wi h he
l
1
me ic,
j
K
n
?
M
n
j 2
O
(
n
3
=
2
)
.
P oo :
The p o o o his esul is based in he ela ion
b e ween he
l
1
and he
l
1
me ics: i we conside a disc
wi h cen e
u
2
R
2
and adio
wi h he
l
1
me ic and
we o a e he plane an angle o
=
4, we ge he disc
wi h cen e
u
and adio
in he
l
1
me ic.
Then, o cons uc he g aph
K
n
?
M
n
o a se o si es
S
in he
l
1
me ic, we only ha e o o a e he plane an
angle o
=
4, cons uc
K
n
?
M
n
in he
l
1
me ic and
o a e he plane again an angle o
?
=
4, as we can see
in Figu e 12.
2
The ques ion ha a ises now is o compa e he wo
me ho ds we ha e gi en o app oxima e he size o
j
K
n
?
104 CCCG 2000, F ede ic on, New B unswick Session C3.2
(a) (b)
(c) (d)
SS'
Figu e 12: (a) A se o si es
S
; (b)
S
o a ed an angle
o
=
4,
S
0
; (c) he g aph
K
n
?
M
n
o
S
0
in he
l
1
me ic;
(d) he g aph
K
n
?
M
n
o
S
in he
l
1
me ic.
M
n
j
. In his way, we in o duce now some esul s o
die en se s o si es, as we can see in Figu e 13, whe e
n
is he size o
S
,
E
1
he edges we sa e using he esul
by E dos and Szeke es and
E
2
he edges we do no use
wi h he me ho d gi en in he p o o o Theo em 6.
n
10
10
10
10
10
2·
3
4
5
6
6
10.705
345.118
10.789.476
338.247.777
954.163.715
600.400
16.999
19.501.264
622.504.000
1.762.505.656
12
E
E
Figu e 13: Some esul s o he size o
K
n
?
M
n
.
4.1 Th ee algo i hms o cons uc
M
n
.
As i was p oin ed ou ab o e, we gi e he e h ee die -
en algo i hms o cons uc ing he g aph
M
n
o any
se o si es in he plane. Bu , as
K
n
?
M
n
and
M
n
a e
complemen a y g aphs, hese algo i hms le us o con-
s uc he g aph
K
n
?
M
n
, o o. In his way, we p esen
he s and he second algo i hms o ge
K
n
?
M
n
and
he hi d one o cons uc
M
n
.
We mus say ha hese h ee algo i hms le us o
cons uc he g aphs
M
n
and
K
n
?
M
n
o a se o si es
in he
l
1
me ic. As we did in Co olla y 7, we only
ha e o o a e he plane an angle o
=
4, cons uc he
g aph
M
n
o
K
n
?
M
n
o he new se o si es and o a e
he plane again an angle o
?
=
4.
4.1.1 The s algo i hm.
The s algo i hm uns in ime
O
(
n
3
) in he wo s
case, bu we hink ha he a e age-case unning ime
is much b e e . This algo i hm is based in he ollowing
asse : Le
S
b e a se o si es in
R
2
. Then i we place
he axis in
u
2
S
we sa e he edges ha join si es in
he s quad an wi h si es in he hi d one. The same
happ ens wi h he si es in he second and he ou h
quad an , as we saw in he p o o o Theo em 6.
So, i we place he axis in all he si es o
S
, we only
ha e o add he edges joining he si es in he p osi ion
we said ab o e o ge ing
K
n
?
M
n
. This is wha he
algo i hm do es. Le
S
b e a se o
n
si es in
R
2
.
Fi s ly, we o de he si es by he second co o dina e
p
1
; p
2
;:::;p
n
, ha can b e done in ime
O
(
n
log
n
).
Secondly, we isi all he si es o
S
om
p
1
o
p
n
.
When we place he axis in a si e
p
j
we conside wo
lis s,
l
T
and
l
B
. In
l
T
we ha e he si es in he second
and he s quad an o de ed by he s co o dina e
and sepa a ed by a p oin e
M
and in
l
B
we ha e he
p oin s o he hi d and he ou h quad an o de ed by
he s co o dina e and sepa a ed by a p oin e
N
. we
can main ain he wo lis s in ime
O
(
n
log
n
).
In he s s ep, we ha e all he si es in
l
T
wi h he
p oin e
M
in he place o
p
1
and in
l
B
we only ha e
he p oin e
N
. Then o
k
= 1
;:::;n
he lis s change
as ollows. In
l
T
we pu
M
in he place o
p
k
. In
l
B
we
add
p
k
?
1
in he place o
N
and we pu
N
in he place
o
p
k
. In Figu e 14 we can see an example o a se o
7 si es.
A las we ha e o add he edges joining he si es on
he le o
M
wi h he si es on he igh o
N
and he
si es on he igh o
M
wi h he si es on he le o
N
ha ha e no b een conside ed ye . Each s ep can b e
done in quad a ic ime, so he whole algo i hm uns in
ime
O
(
n
3
).
4.1.2 The second algo i hm.
The second algo i hm we p esen o cons uc
K
n
?
M
n
uns in ime
O
(
n
2
log
n
) and is based in he ollowing
esul : gi en wo si es
u
and
in he plane, we sa e he
edge
u
i he e is a si e, die en om
u
and
, in he
ec angle ha
u
and
o m, (see Figu e 15).
Then, le
S
b e a se o si es in
R
2
. We conside
a pai o si es
u
and
, we check i he e is ano he
si e in he ec angle ha hey o m and in a ma i e
case, we add he edge
u
. Now, o check i he e is any
si e in a ec angle akes ime
O
(log
n
+
k
), whe e
k
is
he numb e o p oin s inside he ec angle. Bu we s op
when we nd one si e, so each s ep o he algo i hm can
105Session C3.2 12 h Canadian Con e ence on Compu a ional Geome y
p
p
p
p
p
p
p
1
2
3
4
5
6
7
lT={ppp
56
7}
M
l={pp}
B
p
N
2 1 3
p
p
p
p
p
p
p
1
2
3
4
5
6
7
lT={pp6
7}
l={ p p}
Bp
N21 3
M
p
4
S ep 4
S ep 5
Figu e 14: Two s eps o he s algo i hm.
u
w
z
Figu e 15: We sa e he edge
u
, bu no he
w z
.
b e done in
O
(log
n
). As we ha e
n
2
pai s o si es, he
whole algo i hm uns in ime
O
(
n
2
log
n
).
4.1.3 The hi d algo i hm.
He e, we p esen a hi d algo i hm which cons uc s he
g aph
M
n
o a p oin se in he plane. This algo i hm
uns in op imal ime
O
(
n
2
) in he wo s case bu , we
hink ha he a e age-case unning ime is wo s han
he ob ained by he wo algo i hms gi en ab o e.
Wi hou loss o gene ali y, supp ose ha he p oin s
p
1
; p
2
;:::;p
n
g
ha e b een o de ed om le o igh
( ha can b e done in
O
(
n
log
n
)). Fo simplici y, we
spli he algo i hm in wo s eps bu i is no needed
hey a e implemen ed sepa a ely.
The s s ep consis s o cons uc ing a bina y ee
T
wi h
p
1
; p
2
; : : : ; p
n
g
as i s e ices which eco ds he
o de o he p oin s om up o down. Le
p
1
b e he
o o o he ee hen, one o i s descendan sub ees
con ains all he p oin s which a e highe han
p
1
and
he o he sub ee con ains he p oin s which a e lowe .
The ee can b e cons uc ed simply by inse ing he
p oin s successi ely in o de and e e y inse ion akes
ime a mos
O
(log
n
) (see Figu e 16 as an example),
so he whole s ep can b e done in
O
(
n
log
n
). We will
e e ed he sub ees o e e y non-lea no de as i s
high
and
low sub ees
.
Figu e 16: An example o ee
As i was said ab o e, he second s ep can b e done
simul aneously wi h he s one. Conside a p oin
p
j
which ha e b een jus inse ed in he ee. Now, he goal
is o nd he p e ious p oin s which a e joined wi h
p
j
in he g aph
M
n
. Clea ly,
p
j
is joined in
M
n
wi h i s
pa en and wi h he pa en o i s pa en i and only i
p
j
is a low son o a high son o ice e sa. I is no
dicul o check his claim and ha no o he ances o
o
p
j
is joined wi h i in
M
n
.
Now, o e e y ances o
p
i
o
p
j
we will make some
op e a ions. Fo he sake o simplici y, le us supp ose
ha
p
j
is con aining in he low sub ee o
p
i
as you
can see in Figu e 17 ( he o he case is ea ed in a
symme ic way). Nex we will nd he highes lea o
he low sub ee and he lowes one o he high sub ee
and call hem
p
k
and
p
l
esp ec i ely. I
p
k
6
=
p
j
, we se
he a iable
as
k
, o he wise
:= 0.
106 CCCG 2000, F ede ic on, New B unswick Session C3.2
pi
pk
pl
pj
high
sub ee
low
sub ee
Figu e 17: Fo e e y ances o
p
i
o
p
j
, his is one o he
wo p ossible si ua ions.
Finally, we will explo e he no des o he he high
sub ee, b eginning wi h
p
l
in such a way ha a no de is
isi ed a e all o i s i s descendan s ha e b een isi ed.
Fo e e y such no de
p
m
, hen:
I
p
m
is a lea and
m >
, hen he edge
p
j
p
m
b elongs o
M
n
. Also, we se
:=
m
.
I
p
m
is no a lea and i has no low sub ee hen
p
j
p
m
is an edge o he g aph
M
n
Adding he edges o he ee
T
o he nal esul , we
ge he g aph
M
n
. Since in he wo s case, e e y p oin
is needed o b e checked wi h all he p e ious p oin s in
he o de , he whole algo i hm uns in ime
O
(
n
2
) bu
his is op imal.
5 Conclusions and op en p ob-
lems
In his wo k we ha e p o ed ha any (
; =
4)-Yao
g aph con ains he MST o a collec ion o si es in he
l
1
and
l
1
me ics and we ha e s udied wha happ ens
wi h some (
; =
2)-Yao g aphs. I could b e in e es ing
o s udy he es o cases and y o gene alize hese
esul s o o he
l
p
me ics. O he ques ion ela ed wi h
Yao g aphs is o nd upp e b ounds o he dila ion in
hose me ics, as we ha e done o he
l
1
.
We also ha e s udied g aphs wi h dila ion 1 in he
l
1
me ic and he numb e o edges ha we do no need o
cons uc hem. We ha e ob ained ha
j
K
n
?
M
n
j 2
O
(
n
3
=
2
), so he op en ques ion is o nd b e e upp e
b ounds o he size o
K
n
?
M
n
. In ac , we ha e ound
some pa icula cases, o ins ance i he si es a e in
con ex p osi ion, whe e
j
K
n
?
M
n
j 2
O
(
n
2
).
Re e ences
[1]
L.P. Chew.
The e a e plana g aphs almos as
go o d as he comple e g aph.
J. Compu . Sys em.
Sci., 39 (1989), pp. 205{219
[2]
G. Das and D. Joseph.
Which iangula ions ap-
p oxima e he comple e g aph?
P o c. In . Symp.
Op imal Algo i hms, Sp inge LNCS 401 (1989),
pp. 168{192
[3]
G. Das and G. Na asimhan.
A as algo i hm o
cons uc ing spa se Euclidean spanne s.
P o c. 10 h
ACM Symp. Comp. Geom., (1994), pp. 132{139
[4]
D. Eps ein.
Spanning T ees and Spanne s.
Hand-
b o ok o Compu a ional Geome y. Edi ed by J.-R.
Sack and J. U u ia. Else ie Science B. V. (1999),
pp. 425{461
[5]
P. E d
os and A. Szeke es.
A combina o ial
p oblem in geome y.
Comp osi io Ma hema ica,
ol. 2 (1935) 463-470.
[6]
J. M. Keil.
App oxima ing he comple e Eu-
clidean g aph.
P o c. 1s . Scand. Wo ksh. Algo i hm
Theo y, Sp inge LNCS 318 (1988), pp. 208{213.
[7]
C. Le copoulos and A. Lingas.
The e a e pla-
na g aphs almos as go o d as he comple e g aphs
and as sho as minimum spanning ees.
P o c.
In . Symp. Op imal Algo i hms, Sp inge LNCS 401
(1989), pp. 9{13
[8]
A. C. Yao.
On cons uc ing minimum spanning
ees in k-dimensional space and ela ed p oblems.
SIAM J. Compu . (1982), no. 11, pp. 721{736.