Next:
Logic
Up:
Games and Puzzles
Previous:
GP1 MINIMUM GRAPH
-
I
NSTANCE
:
A simple polygon
P
and the visibility polygon
V
of the location of a
robot inside
P
.
-
S
OLUTION
:
A motion scheme for the robot to determine its exact location.
-
M
EASURE
:
The distance the robot travels according to the motion scheme.
-
Good News:
Approximable within
|H|-1
where
H
is the set of points in
P
with
visibility polygon
V
[
94
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997