The polygon exploration problem

Citation
F. Hoffmann et al., The polygon exploration problem, SIAM J COMP, 31(2), 2001, pp. 577-600
Citations number
28
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
2
Year of publication
2001
Pages
577 - 600
Database
ISI
SICI code
0097-5397(20011011)31:2<577:TPEP>2.0.ZU;2-V
Abstract
We present an on-line strategy that enables a mobile robot with vision to e xplore an unknown simple polygon. We prove that the resulting tour is less than 26.5 times as long as the shortest watchman tour that could be compute d off-line. Our analysis is doubly founded on a novel geometric structure called the an gle hull. Let D be a connected region inside a simple polygon, P. We de ne the angle hull of D, AH(D), to be the set of all points in P that can see t wo points of D at a right angle. We show that the perimeter of AH (D) canno t exceed in length the perimeter of D by more than a factor of 2. This uppe r bound is tight.