Authors

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.