Lower bounds for the polygon exploration problem

Lowe Bounds o he Polygon Explo a ion P oblem Ex ended Abs ac Roland Hagius aCh is ian Icking aElma Lange epe b aFe nUni e si ¨a Hagen, P ak ische In o ma ik VI, 58084 Hagen, Ge many bUni e si ¨a Bonn, Ins i u ¨u In o ma ik I, 53117 Bonn, Ge many Abs ac We imp o e he bes known lowe bound o he polygon explo a ion p oblem om 1.2071 o 1.2825. 1. In oduc ion Explo ing an unknown en i onmen is a basic p oblem o au onomous mobile sys ems. He e, we suppose ha a simple polygon in he plane ep esen s he unknown en i onmen and a poin - shaped obo wi h a ision sys em, s a ing a some bounda y poin s, has he ask o going a ound inside he polygon un il he whole en- i onmen has been isible a leas once be o e e u ning o s. Seeing all poin s inside he polygon is clea ly equi alen o seeing i s whole bounda y, as long as he polygon is simple (does no con ain holes, as we assume). The sho es wa chman ou s a ing and ending in sis he sho es ou ha can see he whole polygon, see igu e wa chman. This is he pe ec solu ion in a known en i onmen , and i can be compu ed using he algo i hms o Chin and N a os o Tan and Hi a a [1,3,7,8]. Bu in an unknown en i onmen he sho es wa chman ou is also no known, so any ou ha explo es he polygon online is ine i ably longe han he sho es wa chman ou ; he e a e excep- ions o special cases [2]. So i is an in e es ing ques ion o ask o a s a egy ha p oduces explo- a ion ou s ha a e no so much longe han he pe ec solu ion in a known polygon, and Ho mann e al. [4] ha e gi en such a compe i i e explo a ion s a egy. This s a egy gua an ees a ou ha is a mos 26.5 imes as long as he sho es wa chman ou . Al hough his uppe bound is mos p obably no igh , i is no eally ob ious how o p o e a sho e s Fig. 1. A sho es wa chman ou . ac o by enhancing his a he complica ed p oo o by gi ing a be e s a egy. And he wo s case ha is known o his s a egy has a ac o o jus 5. 2. Fi s ideas o lowe bounds In his pape we p opose o look a his p oblem “ om he o he side”: wha is a lowe bound o his p oblem, i. e., can we show ha no s a egy can gua an ee a compe i i e ac o less han his lowe bound? A p oo o such a bound can be gi en by a conc e e polygon o which we ha e o show ha an a bi a y s a egy will necessa ily make a ce ain de ou as compa ed o he sho es ou . A i ial lowe bound is (√2 + 1)/2≈1.2071, see he le pic u e in Fig. 2: we use an isosceles, ec angula iangle, he s a poin sis a he igh angle and a he o he wo co ne s he e a e wo e y small 20 h EWCG Se ille, Spain (2004) 20 h Eu opean Wo kshop on Compu a ional Geome y ss Fig. 2. De i ing he lowe bounds 1.2071 (le ) and 1.2145 ( igh ). pocke s. One o he pocke s is o med such ha he co ne mus be isi ed while he o he is no . The line segmen connec ing he wo co ne s is called a h eshold. To ick any s a egy o make a de ou we can wai un il his h eshold is eached: i his occu s le o he midpoin hen he igh co ne mus be isi ed, and ice e sa. Thus, only when he obo e en ually isi s he h eshold, i can see which co ne is s ill o isi . Now i is easy o see ha we ha e a lowe bound o (√2 + 1)/2 he e. In ac we can ac as he malicious ad e sa y o a s a egy: depending on he decisions o he s a - egy we decide how he polygon looks like a hose pa s ha ha e no been seen ye . Fo example, he p e ious idea can be e ined by in oducing a second h eshold, see he igh pic u e in Fig. 2. Fi s , we le he s a egy each he line be ween he wo co ne s as be o e. He e, we e eal one o he co ne s, bu in con as o he i s example o he second co ne wo possibili ies emain: ei he we ha e o isi he co ne i sel o i su ices o each he second h eshold which is a diagonal line h ough he co ne . A e ca e ully choosing he leng hs and he angles ( he iangle is s ill isoceles, bu he angle a sis 96.99◦) we ob ain a bound o 1.2145, which cons i u es a small p og ess. 3. Using mo e h esholds Bu his idea o se e al h esholds can be d i en u he . In he ollowing, we ske ch ou app oach wi h h ee h esholds. The basic igu e is a iangle, bu om one o i s co ne s he e a e edges o an inne poin , his will be he s a ing poin s, see Fig. 3. So besides e ex s he e a e ou co ne s in he scene wi h a hidden pocke . The pocke s may be o med such ha he co ne mus be isi ed o no , his is he in o ma ion which is unknown a he s a . Any ou , also he sho es wa chman ou , has o isi a leas all h ee h esholds. I is also clea ha a easonable s a egy will isi he h esholds in he same o de as hey appea along he iangle, o he wise an e en bigge de ou will be gene a ed. Now on each h eshold we place a c i ical poin : i he obo isi s he h eshold o he igh o he c i ical poin (as seen om s) hen we as he ma- licious ad e sa y decide ha he le co ne o he h eshold mus also be isi ed. I he isi occu s o he le o he c i ical poin hen he h eshold is done excep o he las one whe e we decide ha in his case he igh co ne has o be isi ed. We as he ad e sa y a e ee o decide abou he exac shape o he iangle, he placemen o s, and also he placemen o he c i ical poin s. This is a challenging op imiza ion exe cise wi h many deg ees o eedom and se e al in e wo en le els o op imiza ion, which p obably can only be sol ed nume ically. Due o he lack o space we can only b ie ly sum- ma ize ou esul ob ained wi h he help o Cab i Geome y [5,6], see Fig. 4. We use an equila e al iangle (bu i is no clea i his is he bes ) and a s a ing poin sas shown in he igu e. Fo each h eshold he e is one unce ain y, so we ha e eigh cases al oge he . Fo each case we ake he leng h o he sho es wa chman ou and compa e i o he ou passing h ough he c i ical poin s and he co ne s ha ha e o be isi ed in ha case. The minimum o hese eigh a ios which we ha e de- e mined o be a leas 1.2825 is a lowe bound o he explo a ion p oblem. Ma ch 25-26, 2004 Se ille (Spain) wo mo e hidden pocke s he e s Fig. 3. A iangle-like polygon wi h h ee h esholds and ou hidden pocke s. 4. Conclusions The new lowe bound o 1.2825 o he polygon explo a ion p oblem ep esen s a ce ain p og ess, bu we hink ha wi h ou echnique one can go some u he s eps in ha di ec ion. Since he op- imiza ion p oblem p esen ed he e has so many de- g ees o eedom and consis s o se e al le els ha mu ually depend on each o he , we can no be su e, ye , o ha e ound he global op imum o he h ee h esholds. Fu he mo e, i looks p omising, bu edious, o in oduce ou o e en mo e h esholds, bu since he numbe o cases will be abou wo o he powe o he numbe o h esholds, he e is some conside able wo k o be done. Finally, i is in e es ing o no e ha he e is s ill a g ea gap be ween he lowe bound ob ained in his way and he bes known uppe bound o 26.5. Re e ences [1] W.-P. Chin and S. N a os. Sho es wa chman ou es in simple polygons. Disc e e Compu . Geom., 6(1):9–31, 1991. [2] X. Deng, T. Kameda, and C. Papadimi iou. How o lea n an unknown en i onmen I: The ec ilinea case. J. ACM, 45(2):215–245, 1998. [3] M. Hamma and B. J. Nilsson. Conce ning he ime bounds o exis ing sho es wa chman ou e algo i hms. In P oc. 11 h In e na ional Symposium on Fundamen als o Compu a ion Theo y, olume 1279 o Lec u e No es Compu . Sci., pages 210–221. Sp inge - Ve lag, 1997. [4] F. Ho mann, C. Icking, R. Klein, and K. K iegel. The polygon explo a ion p oblem. SIAM J. Compu ., 31:577–600, 2001. [5] J.-M. Labo de. Some issues aised by he de elopmen o implemen ed dynamic geome y as wi h Cab i- g´eom`e e. In Abs ac s 15 h Eu opean Wo kshop Compu . Geom., pages 7–19. INRIA Sophia-An ipolis, 1999. [6] J.-M. Labo de and F. Bellemain. Cab i Geome y II. Texas Ins umen s, Dallas, 1993. [7] X. Tan and T. Hi a a. Cons uc ing sho es wa chman ou es by di ide-and-conque . In P oc. 4 h Annu. In e na . Sympos. Algo i hms Compu ., olume 762 o Lec u e No es Compu . Sci., pages 68–77. Sp inge - Ve lag, 1993. [8] X. Tan, T. Hi a a, and Y. Inagaki. Co igendum o “an inc emen al algo i hm o cons uc ing sho es wa chman ou es”. In e na . J. Compu . Geom. Appl., 9(3):319–323, 1999. 20 h Eu opean Wo kshop on Compu a ional Geome y SWT 24,24 cm SWT 23,39 cm SWT 17,04 cm SWT 20,45 cm SWT 18,24 cm SWT 17,39 cm SWT 13,77 cm SWT 15,97 cm Tou 31,09 cm Tou 30,00 cm Tou 21,87 cm Tou 26,25 cm Tou 23,46 cm Tou 22,35 cm Tou 17,70 cm Tou 20,55 cm C 1,282535654 C 1,2827339161 C 1,283498585 C 1,28371123 C 1,285728851 C 1,28511096 C 1,28541435 C 1,28663922 Fig. 4. Eigh cases o h ee h esholds.