The siphon p oblem
J.M. D´ıaz-B´a˜nez ∗,a,1, C. Sea a b,2and I. Ven u a a,1
aUni e sidad de Se illa, Spain
bUni e si a Poli `ecnica de Ca alunya, Spain
cUni e sidad de Huel a, Spain
Abs ac
An α-siphon is he locus o poin s in he plane ha a e a he same dis ance ǫ om a polygonal chain consis ing
o wo hal -lines emana ing om a common poin such ha αis he in e io angle o he hal -lines. Gi en a se
So npoin s in he plane and a ixed angle α, we wan o compu e an α-siphon o la ges wid h ǫsuch ha no
poin s o Slies in i s in e io . We p esen an e icien O(n2)- ime algo i hm o compu ing an o hogonal siphon.
The app oach can be handled o sol e he p oblem o he o ien ed α-siphon o which he o ien a ion o a hal -line
is known. We also p opose an O(n3log n)- ime algo i hm o he a bi a ily o ien ed e sion.
1. In oduc ion
A co ido h ough a plana poin se Sis he
open egion o he plane ha is bounded by wo
pa allel lines in e sec ing he con ex hull o S,
CH(S). A co ido is emp y i i does no con-
ain any poin o S. The p oblem o compu ing
he wides emp y co ido h ough a se So n
poin s in he plane has been sol ed by Houle and
Maciel [3] in O(n2) ime (Figu e 1a).
One o he possible mo i a ions o he wides
emp y co ido p oblem is o ind a collision- ee
ou e o anspo objec s h ough a se o poin
obs acles. Howe e , e en he wides emp y co i-
do may no be wide enough some imes. This mo i-
a es o conside allowing igh -angle u ns. Chen
in [1] s udied his gene aliza ion conside ing an
L-shaped co ido , which is he conca ena ion o
wo pe pendicula links (a link is composed by wo
pa allel ays and one line segmen o ming an un-
bounded apezoid).
∗Co esponding au ho
Email add esses: [email protected] (J.M. D´ıaz-B´a˜nez),
ca los.sea [email protected] (C. Sea a),
inmaculada. en u a@dma .uhu.es (I. Ven u a).
1The i s au ho is pa ially suppo ed by P ojec MCYT
BFM2000-1052-C02-01.
2The second au ho is pa ially suppo ed by p ojec s
MCYT-FEDER TIC-2001-2171, MCYT-FEDER BFM
2002-0557, Gen Ca 2001SGR00224.
In his pape we conside a kind o co ido p ob-
lem which we call he siphon p oblem. Mo e p e-
cisely, we de ine a siphon as he locus o poin s in
he plane ha a e a he same dis ance ǫ om a
polygonal chain Pconsis ing o wo hal -lines ema-
na ing om a common poin (a 1-co ne polygonal
chain). Le αbe he in e io angle o he hal -lines.
An α-siphon is de ined simila ly bu wi h he con-
s ain ha he in e io angle o he wo hal -lines
emana ing om a common poin is α.
An α-siphon is de e mined by Pand ǫ, whe e ǫ
is called he siphon wid h. Possible alues o he
siphon angle αa e 0◦≤α≤180◦. The α-siphon
p oblem can be s a ed as ollows.
α-Siphon p oblem. Gi en a se So npoin s in
he plane and a ixed angle α, compu e he α-siphon
o la ges wid h such ha no poin s p∈Slies in i s
in e io (Figu e 1b).
The α-siphon has o in e sec he con ex hull
o Sp oducing a non- i ial pa i ion S1,S2o S;
o he wise we will allow he α-siphon “ o sc a ch
he ex e io ” o Swi hou ac ually passing h ough
Sand, he e o e, he α-siphon can be a bi a ily
wide (Figu e 1c).
No ice ha a 180◦-siphon is jus a co ido [3]. A
0◦-siphon is a silo emana ing om a poin ( he end-
poin o a hal -line) (Figu e 1d) and i has been pa -
ially s udied in [2] by gi ing an op imal Θ(nlog n)-
ime algo i hm in he case ha he endpoin o he
hal -line is ancho ed on a gi en poin .
20 h EWCG Se ille, Spain (2004)
20 h Eu opean Wo kshop on Compu a ional Geome y
.
.
.
.
..
.
.
.
.
b)
P
ǫ
❨
ǫ
a)
✐
α
S1
S2
.
.
.
.
..
.
.
.
.
c)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...
.
.
.
.
..
.
.
.
.
..
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
......................ǫ
d)
.........
❨
Fig. 1. a) Wides co ido , b) α-siphon c) unbounded wid h
siphon, c) silo
No ice also ha ou α-siphon is a kind o co i-
do which is a “be e ” solu ion han Cheng’s co -
ido in he ollowing sense: suppose ha we a e
in e es ing in anspo ing a ci cula objec in be-
ween a se o poin s, Cheng’s algo i hm can gi es
a nega i e answe while ou algo i hm p oduces an
a i ma i e answe ; his is so because he wid h o
he wides α-siphon is always la ge han o equal
o he wid h o he wides L-shaped co ido ; in
ac a siphon is he a ea swep by a disk whose
cen e desc ibes he ou e.
In his pape wo a ian s o he α-siphon p ob-
lem a e conside : i) he o ien ed α-siphon p oblem,
whe e we know he angle αand he di ec ion o one
o he hal -lines o P; ii) he a bi a ily o ien ed α-
siphon p oblem, whe e only he angle αis known.
Mos p oo s a e omi ed in his ex ended abs ac .
Le S={p1, p2,...,pn}be a plana poin se .
The poin s a e in gene al posi ion, his assump ion
is no essen ial o ou algo i hms o wo k, bu han-
dling degene acies would equi e he desc ip ion o
many de ails and would hide he c ucial ideas. We
deno e he Euclidean dis ance be ween wo poin s
pand qby d(p, q). I pis a poin and Pis a closed
subse in he plane, he dis ance be ween pand P
is de ined as d(p, P) = min{d(p, q) : q∈P}.
An α-siphon is bounded by an ou e bound-
a y and an inne bounda y; he ou e bounda y is
o med by a ci cula a c joined o wo hal -lines,
he ex e io bounda y legs; and he inne bounda y
is o med by wo hal -lines, he in e io bounda y
legs. By o hogonal siphon we deno e an o ien ed
90◦-siphon such ha i s bounda y legs a e e ical
and ho izon al.
2. O ien ed α-siphon
In his sec ion we s udy he p oblem o compu -
ing an o ien ed α-siphon. Fi s we conside he o -
hogonal siphon and nex we will conside he gen-
e al case. The e a e ou possibili ies o Pin an
o hogonal siphon acco ding o he no h, sou h,
eas and wes di ec ions. We only conside he case
S-E, o he cases can be handle analogously.
Fi s no ice ha o any 1-co ne polygonal
chain Pwhich does no con ain poin s om S
and p oduces a non- i ial pa i ion o S, always
exis s a siphon de ined by P. We call a siphon
non-expansi e i i s in e io bounda y con ains
wo poin s o S(one pe each leg o only one poin
i his poin is on he e ex o ha bounda y) and
i s ex e io bounda y con ains one poin o S.
Lemma 1 Fo any ixed e ical and ho izon al
lines c ossing he con ex hull o Sp oducing a non
i ial pa i ion o S, he e exis s a non-expansi e
siphon.
Nex we desc ibe he algo i hm which sol es he
S-E o hogonal siphon p oblem in O(n2) ime. By
Lemma 1 we know ha an o hogonal siphon is de-
ined by a mos h ee poin s. Fi s , he algo i hm
so s he poin s in Sby dec easing y-coo dina e
and by inc easing x-coo dina e in O(nlog n) ime.
Le O={p1,...,pn}and A={q1,...,qn}be
he espec i e lis s o he so ed poin s. F om a
e ical-ho izon al g id we cons uc a S-E s ai -
case Ewhich is upda ed each ime we inse a new
poin , and in his case ei he he numbe o he
s eps o Einc ease by one o i dec ease because
he new poin domina es some poin s o he cu -
en E.
Le p1and q1be he poin s o Swi h maxi-
mum y-coo dina e and minimum x-coo dina e, e-
spec i ely. These wo poin s de e mine he s a -
ing poin o he algo i hm. The s ai case Ein he
ini ial s age is o med by he ho izon al and e -
ical hal -lines o he g id passing h ough p1and
q1. The algo i hm compu e all he possible o hog-
onal siphons which ho izon al bounda y leg is sup-
po ed by pi∈O, o i= 2,...,n. I a poin
pi= (xpi, ypi) is on he ho izon al-in e io bound-
a y leg o a siphon hen, he e only exis siphons
such ha i s “en ies” a e in-be ween poin s ha -
ing x-coo dina es and y-coo dina es smalle han
o equal o xpi and ypi, espec i ely; because he
es o poin s ei he a e domina ed by ei he he
cu en s ai case o he poin pi. The dominance
ela ion be ween poin s o Sis es ablish as in [4,5].
In [5] he maxima p oblem o a se o poin s is con-
side ed. The maxima p oblem consis s o inding
all he maxima o Sunde dominance and hey can
be compu ed in θ(nlog n) ime. We a e in e es ed
Ma ch 25-26, 2004 Se ille (Spain)
in he maxima p oblem wi h he ollowing domi-
nance ela ion: pj≺pi⇐⇒ xpj ≤xpi and ypj ≥
ypi.The co esponding se o maxima o ms a ou
quad an s ai case.
We cons uc he s ai case Ein an inc emen-
al way wi h a cos o O(log n) ime pe poin in-
se ion. In he wo s case he numbe o di e en
siphons o be checked can be O(n2). Assume ha
Oand Aha e been compu ed and also o each
poin piwe ha e a poin e o qlsuch ha pi=ql.
ORTOGONAL-SIPHON-ALGORITHM
Inpu : S,O,A,
Ou pu : Wides o hogonal siphon,
(i) Ini ial s age: O,A,E:= s ai case o med
by he ho izon al and e ical hal -lines de-
ined by q1and p1. Compu e he Vo onoi di-
ag am o S,V D(S), and s o e i in a da a
s uc u e such ha a que y poin can be an-
swe ed in O(log n) ime.
(ii) Fo i= 2 o n,do “Compu e he wides
o hogonal siphon suppo ed by piand qj,
such ha xqj< xpi,yqj< ypi”,
Le ǫ1be he dis ance be ween y=ypi
and he ho izon al line con aining he seg-
men o he cu en Ewhich is in e sec ed
by x=xqj. Compu e ǫ2=xqj −xq(j−1) and
ǫ0= min{ǫ1, ǫ2}. The o hogonal siphon sup-
po ed by piand qjhas wid h smalle han
o equal o ǫ0/2. Compu e he pa Eij o E
in-be ween he x-coo dina es xqj −ǫ0and xqj
and he y-coo dina es ypi and ypi +ǫ0. Check
ha Eij is emp y and compu e he o hogo-
nal siphon o wid h ǫ0/2 suppo ed by piand
qj. O he wise, we analyze each poin o Eij
de e mining (i i exis s) he co esponding
o hogonal siphon as ollows:
The e ex o he 1-co ne polygonal line
o he siphon will be loca ed in he bisec-
o o he second quad an passing h ough
(xqj, ypi). This e ex is he cen e o he ci -
cle which con ains he a c o he siphon. By
using Eand V D(S), we conside each o he
h ee possible loca ions o he poin belong-
ing o he ex e io bounda y.
(iii) Upda ing s age: Inse piin Eand upda e
Ein ime O(log n) pe inse ion and in o-
al ime O(nlog n) o he dele ion o poin s
om E(a poin is dele ed only once). Dele e
pi om O, dele e ql=pi om A, upda e he
wides wid h and he cu en siphon.
Lemma 2 Each e ex cio he s ai case Eis an-
alyzed a mos once.
Analysis o he algo i hm: The numbe o s ages is
O(n2). A he s age (i, j) we check all he e ices
in Eij in O(log n) ime. By Lemma 2 a e ex in E
is analyzed only once, hen he o al ime cos in
he analysis o poin s in Eis O(nlog n). The e o e
he unning ime o he algo i hm is O(nlog n) +
O(n2) = O(n2).
Theo em 3 The wides o hogonal siphon can be
compu ed in O(n2) ime.
The echniques abo e can be adap ed o com-
pu ing he wides o ien ed α-siphon, i.e., a α-
siphon wi h a gi en angle α, 0 < α < 180◦and a
ixed di ec ion o one o i s hal -lines.
Co olla y 4 The wides o ien ed α-siphon can be
compu ed in O(n2) ime.
Theo em 5 The p oblem o compu ing he wides
o ien ed α-siphon has an Ω(nlog n) ime lowe
bound in he algeb aic decision ee model.
No ice ha he complexi y o he algo i hm
abo e ma ch he complexi y o he algo i hm o
compu ing he wides co ido o a se o poin s.
A small a ia ion o he algo i hm abo e can be
used o compu e he wides L-shaped o hogonal
co ido (as de ined by Chen [1]) wi h he same
O(n2) unning ime.
Co olla y 6 The wides L-shaped o hogonal co -
ido can be compu ed in O(n2) ime.
A simila algo i hm can be used i we wan o
compu e a co ido o he same kind bu wi h an
angle di e en om 90◦and knowing he di ec ion
o one o he links.
3. The a bi a ily-o ien ed α-siphon
In his sec ion we deal wi h he compu a ion o
a wides -emp y a bi a ily-o ien ed α-siphon, i.e.,
we only ix he siphon angle α. Assume ha αis π
2.
Lemma 7 The e always exis s an op imal π
2-
siphon such ha he in e io bounda y con ains
wo poin s o S(one pe each leg) o only one poin
i his poin is on he co ne o ha bounda y.
The poin s in S ha de e mine a en a i e place-
men o an op imal α-siphon a e called he c i ical
poin s. The e o e we can classi y he cases o c i -
ical poin s acco ding o hei loca ion on he pa s
o he siphon, as i is shown in Figu e 2.
20 h Eu opean Wo kshop on Compu a ional Geome y
(1)
(3) (4)
(5) (6)
(2)
Fig. 2. Types o candida e siphons.
We ske ch he idea o ou app oach wi hou de-
ails. We only conside siphons ha a e bounded
by a poin o each i s in e io hal -lines (acco ding
o Lemma 7). The o ien a ion θo ou siphon is he
smalle o he wo angles gi en by he o ogonal
lines suppo ing he in e io bounda y legs. Gi en
wo poin s pi,pj(xpi> xpj), we conside he o-
a ion o he wo pe pendicula lines i(θ) (a ound
pi) and sj(θ) (a ound pj), say coun e clockwise, o
ob ain all possible emp y siphon suppo ed a pi
and pj. The essence o ou algo i hm is o gene a e
a disc e e se o subin e als in such o a ion and
compu e a siphon o maximum wid h o each.
We begin he o a ion in θ= 0. A pai o o hog-
onal lines h ough piand pjpa i ions he poin se
in o ou disjoin subse s which we label I,II,III
and IV (co esponding o he ou quad an s). As
we change he o ien a ion con inuously, he pa i-
ion su i e ill some wo poin s become collinea .
In ac , by inse ion and dele ion o he poin s,
we can main ain dynamically each one o he co -
esponding pa i ion. This spend O(n2) ime and
space. This p oduces a pa i ion o he o a ion in-
e al. Taking in o accoun he in e als o such
pa i ions o each poin pk∈S, we de ine he ol-
lowing unc ions:
–uk(θ) = d(pk, i(θ)), o pk∈I,
–uk(θ) = d(pk, i(θ)), lk(θ) = d(pk, sj(θ)) and
ck(θ) = d(pk, cijk(θ)), o pk∈II,
–lk(θ) = d(pk, sj(θ)), o pk∈III,
whe e cijk(θ) is he cen e o he ci cle passing
h ough pk angen o he lines i(θ) and sj(θ).
Lemma 8 Le pkand plbe wo dis inc poin s o
S. Then, he g aphs o wo unc ions co esponding
o pkand plin e sec a mos wice.
Le Lbe he lowe en elope o he g aphs o
he unc ions uk, lkand ck. Lemma 8 implies ha
he labels o he poin s co esponding o he edges
o L, when we a e se L om le o igh , o m
a Da enpo -Schinzel sequence o o de wo [6].
The e o e, he numbe o in e als in he pa i ion
is O(n) [6], and by using a s anda d di ide-and-
conque app oach we can compu e Lin O(nlog n)
ime. Thus, by a e sing L, om le o igh , we
can iden i y he highes e ex, which co esponds
o he op imal di ec ion o he π
2-siphon. In sum-
ma y, wo king o e all pai o poin s in S, we ha e
p o en he ollowing esul .
Theo em 9 Gi en a se So npoin s in he plane,
he wides emp y a bi a ily-o ien ed π
2-siphon can
be compu ed in O(n3log n) ime.
An adap a ion o abo e app oach pe mi s o
sol e he p oblem o a ixed angle α, 0◦≤α≤
180◦in he same ime bound.
A cons ained e sion o his p oblem consis s
in o ancho ing he e ex o he 1-co ne polygonal
chain. In his case we ob ain he ollowing esul .
Theo em 10 Gi en a se So npoin s in he
plane, he wides -emp y a bi a ily-o ien ed an-
cho ed α-siphon can be compu ed in op imal
Ω(nlog n) ime.
Re e ences
[1] S-W. Chen, Wides emp y L-shaped co ido ,
In o ma ion P ocessing Le e s, 58, 1996, pp. 277–283.
[2] F. Folle , E. Sch¨ome , J. Sellen, M. Smid, C. Thiel,
Compu ing he la ges emp y ancho ed cylinde , and
ela ed p oblems, In e . Jou nal o Compu . Geome y
and Aplica ions, Vol. 7 (6), 1997, pp. 563–580.
[3] M. E. Houle, A. Maciel, Finding he wides emp y
co ido h ough a se o poin s, in Snapsho s
o Compu a ional and Disc e e Geome y, God ied
Toussain , ed., Technical Repo SOCS-88.11, School o
Compu e Science, McGill Uni e si y, 1988.
[4] H. T. Kung, F. Luccio, F. P. P epa a a, On inding
he maxima o a se o ec o s, Jou nal o ACM, 22(4),
1975, pp. 469–476.
[5] F. P. P epa a a, M. I. Shamos, Compu acional
Geome y, An in oduc ion, Sp inge -Ve lag, 1988.
[6] M. Sha i , P. K. Aga wal, Da enpo -Schinzel sequences
and hei geome ic applica ions, Camb idge Uni e si y
P ess, 1995.