The siphon problem

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.