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.