Tiko Kameda (SFU)
08/08/14 12:30 Talks
Polygon search problems
Speaker:
Tiko Kameda (Simon Fraser University)
Abstract:
Suppose intruders are in a dark polygonal room and they can move arbitrarily fast, trying to avoid detection. The boundary1-searcher is equipped with a flash light that he can direct in any direction, but his movement is constricted to be on the polygon boundary. A polygon is {\em 1-searchable} if there is a schedule for the searcher to follow in order to always detect the intruders who can move faster than the rotational movement of the flashlight beam. A simple set of {\em forbidden patterns} is known such that a given polygon is searchable by the boundary 1-searcher iff none of them is present.
We will also discuss the (non-boundary) k-searcher with k flush lights, which can be directed independently of each other, as well as the $\infty$-searcher, who has an omnidirectional light source that shines in all directions. We compare the searching capabilities of the k-searchers for k=1,2 and $\infty$, and also talk about the complexity of testing if a given polygon is searchable by any of these searchers.
Date:
Friday, August 8, 2014
Time:
12:30 pm - 1:30 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby
Tiko Kameda (Simon Fraser University)
Abstract:
Suppose intruders are in a dark polygonal room and they can move arbitrarily fast, trying to avoid detection. The boundary1-searcher is equipped with a flash light that he can direct in any direction, but his movement is constricted to be on the polygon boundary. A polygon is {\em 1-searchable} if there is a schedule for the searcher to follow in order to always detect the intruders who can move faster than the rotational movement of the flashlight beam. A simple set of {\em forbidden patterns} is known such that a given polygon is searchable by the boundary 1-searcher iff none of them is present.
We will also discuss the (non-boundary) k-searcher with k flush lights, which can be directed independently of each other, as well as the $\infty$-searcher, who has an omnidirectional light source that shines in all directions. We compare the searching capabilities of the k-searchers for k=1,2 and $\infty$, and also talk about the complexity of testing if a given polygon is searchable by any of these searchers.
Date:
Friday, August 8, 2014
Time:
12:30 pm - 1:30 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby