Op imal Spanne s o Axis-Aligned Rec angles 1
Te suo Asano aMa k de Be g bO ied Cheong bHazel E e e cHe man Ha e ko d
Naoki Ka oh eAlexande Wol
aJAIST, Japan
bTU Eindho en, he Ne he lands
cLORIA, F ance
dU ech Uni e si y, he Ne he lands
eKyo o Uni e si y, Japan
Uni e si ¨a Ka ls uhe, Ge many
1. In oduc ion
Geome ic ne wo ks a ise equen ly in ou e -
e yday li e: oad ne wo ks, elephone ne wo ks,
and compu e ne wo ks a e all examples o geo-
me ic ne wo ks ha we use daily. They also play
a ole in disciplines such as VLSI design and mo-
ion planning. Almos in a iably, he pu pose o
he ne wo k is o p o ide a connec ion be ween
he nodes in he ne wo k. O en i is desi able
ha he connec ion h ough he ne wo k be ween
any pai o nodes be ela i ely sho . F om his
iewpoin , one would ideally ha e a di ec con-
nec ion be ween any pai o nodes. This is usually
in easible due o he cos s in ol ed, so one has o
comp omise be ween he quali y and he cos o
he connec ions.
Fo wo gi en nodes in a g aph, he a io o hei
dis ance in he g aph and hei ‘di ec ’ dis ance is
called he dila ion o s e ch ac o o ha pai
o nodes, and he dila ion o a g aph is he maxi-
mum dila ion o e all pai s o nodes. Fo geome ic
ne wo ks, his is mo e p ecisely de ined as ollows.
Le Sbe a se o npoin s (in he plane, say), and
le Gbe a g aph wi h node se S. Now he dila ion
o a pai o poin s p, q is de ined as he a io o he
Email add esses: -asano@jais .ac.jp (Te suo
Asano), m. .d.be g@ ue.nl (Ma k de Be g),
ocheong@win. ue.nl (O ied Cheong),
e e e @lo ia. (Hazel E e e ), he [email protected]
(He man Ha e ko ), naoki@a chi.kyo o-u.ac.jp (Naoki
Ka oh), awol @i a.uka.de (Alexande Wol ).
1Pa o his esea ch was done du ing he Fi s
U ech -Ca le on Wo kshop on Compu a ional Geome y.
H.H. acknowledges suppo by he Ne he lands’ O ganiza-
ion o Scien i ic Resea ch (NWO).
leng h o he sho es pa h in Gbe ween pand q,
and he leng h o he segmen pq. (The leng h o a
pa h is he sum o he leng hs o i s edges.) Again,
he dila ion o Gis he maximum dila ion o e all
pai s o poin s in S. A g aph wi h dila ion is
called a -spanne . Ideal ne wo ks a e -spanne s
o small wi h small cos .
Spanne s we e in oduced by Peleg and Sch¨a e [6]
in he con ex o dis ibu ed compu ing, and by
Chew [1] in he con ex o compu a ional geome-
y. They ha e a ac ed much a en ion since—
see o ins ance he su ey by Epps ein [2]. The
cos o spanne s can be measu ed acco ding o a -
ious c i e ia. Fo example, i is some imes de ined
as he numbe o edges (he e he goal is o ind a
spanne wi h O(n) edges), o as he o al weigh
o he edges (he e he goal is o ind a spanne
whose o al weigh is a cons an imes he weigh
o a minimum spanning ee). Addi ional p ope -
ies, such as bounding he maximum deg ee o he
diame e , ha e been conside ed as well.
We gene alize he no ion o spanne s o geo-
me ic ne wo ks whose nodes a e ec angles a he
han poin s. Le Sbe a se o nnon-in e sec ing,
axis-pa allel ec angles and le Ebe a se o axis-
pa allel segmen s connec ing pai s o ec angles.
Fo any wo poin s p, q in he union o he ec -
angles, he dila ion is now he a io o he leng h
o he sho es ec ilinea pa h in he ne wo k be-
ween pand qand hei L1-dis ance. He e a pa h in
he ne wo k is a pa h ha s ays wi hin he union
o he ec angles and he connec ing segmen s. The
dila ion o he ne wo k is he maximum dila ion
o e all pai s p, q. Again, ou aim is o cons uc a
ne wo k whose dila ion is small. To illus a e he
concep , imagine one is gi en a numbe o ec -
20 h EWCG Se ille, Spain (2004)
20 h Eu opean Wo kshop on Compu a ional Geome y
angula buildings, which ha e o be connec ed by
oo b idges. I is qui e us a ing i , o walk o a
oom opposi e ones own oom in an adjacen build-
ing, one has o walk all he way o he end o a
long co ido , hen along he oo b idge, and hen
back again along he co ido in he o he building.
Hence, one would usually place he oo b idge in
he middle be ween buildings. Following his anal-
ogy, we will call he ec angles in he inpu build-
ings om now on, and he connec ing segmen s
b idges. We call he unde lying g aph o he ne -
wo k he b idge g aph.
The gene aliza ion we s udy in oduces one im-
po an addi ional di icul y in he cons uc ion o
a spanne : o poin s one only has o decide which
edges o choose in he spanne , bu o buildings,
one also has o decide whe e o place he b idge
be ween a gi en pai o buildings. I is he la e
p oblem we ocus on in his pape : we assume he
opology o he ne wo k ( he b idge g aph) is gi en,
and ou only ask is o place he b idges so as o
minimize he dila ion.
Fo mally, ou p oblem can be s a ed as ollows:
we a e gi en a se So axis-pa allel disjoin ec -
angles (buildings) in he plane, a g aph Gwi h
node se S, and o each a c eo Gab idge e-
gion Λe, an axis-aligned ec angle connec ing he
wo buildings. Buildings may degene a e o seg-
men s o poin s. The b idge g aph Gmus only
ha e a cs be ween buildings ha can be connec ed
by a ho izon al o e ical segmen , and may no
ha e mul iple edges o loops. The b idge egions
mus be disjoin om each o he and he buildings.
Ou goal is o ind a se o ho izon al o e ical
b idges lying in he b idge egions ha has mini-
mum dila ion.
Figu e 1 shows a b idge g aph ( he b idge e-
gions a e shaded) and a se o possible b idges.
No e ha he b idge egions Λ2and Λ3simply
allow any b idge be ween he wo buildings, bu
b idge egion Λ1has been chosen so as o a oid
in e sec ing s4o he b idge be ween s3and s4.
Ou esul s a e as ollows.
•In gene al, he p oblem is NP-ha d.
•I he b idge g aph is a ee, hen he p ob-
lem can be sol ed by a linea p og am wi h
O(n2) a iables and cons ain s.
•I he b idge g aph is a pa h, hen he p ob-
lem can be sol ed in O(n3log n) ime.
•I he b idge g aph is a pa h and he build-
ings a e so ed e ically along his pa h, he
p oblem can be sol ed in ime O(n2). A (1 +
ε)-app oxima ion can be compu ed in linea
ime.
s1
s2
s3
s4
Λ1
Λ2
Λ3
Fig. 1. A b idge g aph and a b idge con igu a ion
2. The b idge g aph is a bi a y
The b idge-placemen p oblem is NP-ha d i he
b idge g aph is allowed o be a bi a y. We p o e
his by a educ ion om Pa i ion. The inpu o
Pa i ion is a se Bo nposi i e in ege s, and
he ask is o decide whe he Bcan be pa i ioned
in o wo subse s o equal sum. Pa i ion is NP-
ha d [3, P oblem SP12].
Theo em 1 I is NP-ha d o decide whe he he
b idges in a gi en b idge g aph on n ec angula
buildings can be placed such ha he dila ion is a
mos 2.
3. The b idge g aph is a ee
In his sec ion we will show ha he b idge-
placemen p oblem can be sol ed by a linea p o-
g am i he b idge g aph is a ee. We s a by in-
oducing some e minology and no a ion, and by
p o ing some basic lemmas. As be o e, we deno e
he b idge g aph by G. Any se o b idges ealiz-
ing Gwill be called a con igu a ion.
p
q
π(p, q,B)
kpqk
Fig. 2.
Ma ch 25-26, 2004 Se ille (Spain)
Fig. 3.
Gi en a con igu a ion Band wo poin s pand q
in he union o all buildings, we use π(p, q, B) o de-
no e he amily o ec ilinea sho es pa hs om p
o qwi hin he con igu a ion ( ha is, pa hs whose
links lie inside buildings o on b idges). The pa hs
o his amily a e essen ially he same, hey di -
e only in how hey connec wo poin s inside he
same building, and so we will simply speak abou
he unique pa h π(p, q, B). The dila ion o he pa h
π=π(p, q, B) is dil(π) := |π|/kpqk, whe e |π|is
he o al leng h o πand kpqkis he L1-dis ance
o pand q. Figu e 2 shows a con igu a ion and an
example pa h.
The dila ion dil(B)o a con igu a ion Bis de-
ined as he maximum dila ion o any pa h wi h
espec o B. Ou aim is o ind a con igu a ion
o minimum dila ion. We i s cha ac e ize pai s
o poin s ha a e esponsible o he dila ion o a
gi en con igu a ion.
Lemma 2 Le σbe he dila ion o a con igu a-
ion Bwhose unde lying g aph is a ee. Then he e
a e poin s pand qwi h dil(π(p, q, B)) = σsuch ha
he closed bounding box o pand qdoes no con ain
any poin o a building o he han pand q, and a
leas one o he poin s pand qis a building co ne .
A poin pai (p, q) as in he lemma—i s bounding
box con ains no o he poin o any building and
a leas one o pand qis a building co ne —will
be called a isible pai —see Figu e 3 o examples.
We deno e he se o all isible pai s by V.
Gi en a b idge g aph G, ou goal is o minimize
max
(p,q)∈V dil(π(p, q, B))
o e all con igu a ions B ealizing G. We show ha
his p oblem can be e o mula ed as a linea p o-
g am.
Theo em 3 I he b idge g aph Gis a ee, hen
a placemen o he b idges ha minimizes he di-
la ion can be compu ed by sol ing a linea p og am
wi h O(n2) a iables and cons ain s, whe e nis
he numbe o b idges in he b idge g aph.
4. The b idge g aph is a pa h
In he p e ious sec ion we ha e gi en a linea
p og am o he b idge-placemen p oblem o he
case whe e he b idge g aph is a ee. Linea p o-
g ams can be sol ed in p ac ice, and o in ege
coe icien s, in e io -poin me hods can sol e hem
in ime polynomial in he bi -complexi y o he in-
pu [4]. I is no known, howe e , i hey can be
sol ed in polynomial ime on he eal RAM, he
s anda d model o compu a ional geome y. In his
sec ion, we gi e polynomial ime algo i hms o he
case whe e he b idge g aph is a pa h.
Since he b idge g aph Gis a pa h, we can num-
be he buildings and b idges so ha b idge bicon-
nec s buildings si−1and si, o 1 ≤i≤n(so he e
a e n+ 1 buildings and nb idges). Be o e we con-
inue, we need o in oduce some mo e e minol-
ogy. We conside a pa h π=π(p, q, B) o be o i-
en ed om p o q. A e a e sing a b idge b, he
pa h can con inue s aigh on o a e se he nex
b idge b′i band b′a e collinea . In all o he cases,
i has o u n.
b9
b10 b8
b12
b13
p
π
b1
b2
b4
b6
b7
b11
b14
q
s6
b5
b3
s10
s1
Fig. 4. U- u ns and hei ou e sides
Gi en a pa h π, a link ℓo πis a maximal s aigh
segmen o he pa h. A link can con ain mo e han
one b idge i hey a e collinea . Fo example, in
Figu e 4 he e is a link con aining b1and b2, and
ano he link con aining b8,b9, and b10.
The pa h π u ns a bo h ends o a link (excep
o he i s and las link). The link is a igh U-
u n i π u ns igh be o e and a e he link. A
le U- u n is de ined symme ically. In Figu e 4,
he links con aining b idges (b1, b2), (b4, b5), and
b12 a e igh U- u ns, while he links con aining
b7, (b8, b9, b10), b11, and (b13, b14) a e le U- u ns.
No e ha he e can be U- u ns ha do no con ain
20 h Eu opean Wo kshop on Compu a ional Geome y
any b idges, as he link o πinside building s6in
Figu e 4.
The inne side and ou e side o a U- u n
a e ec angula egions in ini e on one side, and
bounded by he line suppo ing he link and he
wo lines o hogonal o i h ough he i s and
las poin s o he link. The ou e side lies locally
o he le o a igh U- u n, o o he igh o a
le U- u n, he inne side lies locally o he igh
o a igh U- u n o o he le o a le U- u n. In
Figu e 4, he ou e sides o all U- u ns a e shaded.
U- u ns a e he links o a pa h ha de e mine
i s dila ion, as he ollowing lemma shows.
Lemma 4 Le Band B′be con igu a ions, (p, q)
a isible pai , and π:= π(p, q, B)and π′:=
π(p, q, B′) he pa hs be ween pand qwi h espec
o he wo con igu a ions. I dil(π′)<dil(π) hen
he e exis s a U- u n ℓcon aining bi...bjo πsuch
ha he co esponding b idges b′
i,...,b′
jo B′lie
s ic ly on he inne side o ℓ.
We will gi e an algo i hm ha akes as inpu he
se o buildings s0,...,snand a eal numbe σ > 1,
and compu es a con igu a ion Bwi h dil(B)≤σ,
o de e mines ha no such con igu a ion exis s.
The algo i hm compu es nse s I1, I2,...,In,
whe e Iiis a se o possible b idges be ween
si−1and si. The se s a e de ined ecu si ely
as ollows. Assume ha I1,...,Ii−1ha e al-
eady been de ined. Fo each isible pai (p, q)
wi h p∈Si−1
j=0 sjand q∈siwe de ine I(p, q)
as he se o b idges biconnec ing si−1and si
such ha he ollowing holds: he e is a se o
b idges b1∈I1, b2∈I2, ...,bi−1∈Ii−1such
ha dil(π(p, q, (b1,...,bi))) ≤σ. Finally, Iiis he
in e sec ion o all I(p, q).
No e ha o each isible pai (p, q) we can
choose he b idges in I1,...,Ii−1independen ly.
This makes i possible o compu e Iie icien ly, as
we will see below. On he o he hand, i implies
ha no e e y sequence o b idges chosen om
he se s will be a con igu a ion wi h dila ion a
mos σ—ou main lemma will be o show ha
such a sequence does indeed exis .
Once we know I1,...,In, we can ecu si ely
compu e a con igu a ion wi h dila ion a mos σ:
Choose an a bi a y b idge bn∈In. I b idges
bn−1, bn−2,...,bi+1 ha e been compu ed, choose a
b idge bi∈Iiwhose dis ance om bi+1 is minimal.
Since Iiis an “in e al o b idges”, his implies
ha ei he biand bi+1 a e collinea , o biis one o
he ex eme b idges in Ii. We now p o e ha his
app oach is co ec .
Lemma 5 Le I1,...,Inbe gi en as de ined abo e.
A con igu a ion Bwi h dila ion dil(B)≤σexis s
i and only i In6=∅. I i exis s, i can be compu ed
in O(n) ime om he in e als.
Lemma 6 The in e als I1,...,Inde ined abo e
can be compu ed in O(n2) ime and O(n)space.
Lemmas 6 and 5 imply he ollowing heo em.
Theo em 7 Gi en a b idge g aph Gon a se o
n+1 buildings ha is a pa h and a eal numbe σ >
1, we can in ime O(n2)compu e a con igu a ion B
ealizing Gwi h dil(B)≤σo de e mine ha no
such con igu a ion exis s.
I seems ha d o imp o e his esul when he e
a e Θ(n2) isible pai s ha could de e mine he
dila ion. In ac , we do no e en know how o decide
in o(n2) ime whe he a gi en con igu a ion has
dila ion ≤σ. I he numbe ko isible pai s o he
gi en se o buildings is o(n2/log n), he unning
ime can be imp o ed o O(klog n).
We sol e he o iginal op imiza ion p oblem using
Megiddo’s pa ame ic sea ch [5].
Theo em 8 Gi en a b idge g aph on a se o n+1
buildings ha is a pa h, we can compu e a con igu-
a ion wi h he op imal dila ion in ime O(n3log n),
o in ime O(nk log2n), whe e kis he numbe o
isible pai s.
Re e ences
[1] L. P. Chew. The e a e plana g aphs almos as good as
he comple e g aph. J. Compu . Sys . Sci., 39:205–219,
1989.
[2] Da id Epps ein. Spanning ees and spanne s. In J¨o g-
R¨udige Sack and Jo ge U u ia, edi o s, Handbook
o Compu a ional Geome y, pages 425–461. Else ie
Science Publishe s B.V. No h-Holland, Ams e dam,
2000.
[3] M. R. Ga ey and D. S. Johnson. Compu e s
and In ac abili y: A Guide o he Theo y o NP-
Comple eness. W. H. F eeman, New Yo k, NY, 1979.
[4] N. Ka ma ka . A new polynomial- ime algo i hm o
linea p og amming. Combina o ica, 4:373–395, 1984.
[5] N. Megiddo. Applying pa allel compu a ion algo i hms
in he design o se ial algo i hms. J. ACM, 30(4):852–
865, 1983.
[6] D. Peleg and A. Sch¨a e . G aph spanne s. J. G aph
Theo y, 13:99–116, 1989.