An Efficient Competitive Strategy for Learning a Polygon
Frank Hoffmann, Christian Icking, Rolf Klein, Klaus Kriegel
Institut für Informatik
Freie Universität Berlin
email: hoffmann, kriegel@inf.fu-berlin.de
FernUniversität Hagen
Praktische Informatik VI
email: Rolf.Klein@FernUni-Hagen.de, Christian.Icking@FernUni-Hagen.de
Report B 96-01
February 1996
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-96-01.ps.gz
An Efficient Competitive Strategy for Learning a Polygon
We provide a competitive strategy for a mobile robot with vision, that has to explore an unknown simple polygon starting from and returning to a given point x0 on the boundary. Our strategy creates a tour that does not exceed in length 133 times the length of the shortest watchman route from x0. It has been claimed before by other authors that a competitive strategy with factor 2016 exists for this problem; but no proof has appeared except for the easy rectilinear case.