ProV Logo
0
Line-of-Sight Pursuit in Monotone and Sc...
Berry, Lindsay...

Free

Line-of-Sight Pursuit in Monotone and Scallop Polygons by Berry, Lindsay ( Author )
Lemonjar Open Access
N.A
30-08-2015
We study a turn-based game in a simply connected polygonal environment Q between a pursuer P and an adversarial evader E. Both players can move in a straight line to any point within unit distance during their turn. The pursuer P wins by capturing the evader, meaning that their distance satisfies d(P,E)≤1, while the evader wins by eluding capture forever. Both players have a map of the environment, but they have different sensing capabilities. The evader E always knows the location of P. Meanwhile, P only has line-of-sight visibility: P observes the evader's position only when the line segment connecting them lies entirely within the polygon. Therefore P must search for E when the evader is hidden from view. We provide a winning strategy for P in two families of polygons: monotone polygons and scallop polygons. In both families, a straight line L can be moved continuously over Q so that (1) L∩Q is a line segment and (2) every point on the boundary ∂Q is swept exactly once. These are both subfamilies of strictly sweepable polygons. The sweeping motion for a monotone polygon is a single translation, and the sweeping motion for a scallop polygon is a single rotation. Our algorithms use rook's strategy during its pursuit phase, rather than the well-known lion's strategy. The rook's strategy is crucial for obtaining a capture time that is linear in the area of Q. For both monotone and scallop polygons, our algorithm has a capture time of O(n(Q)+area(Q)), where n(Q) is the number of polygon vertices.
-
Article
pdf
36.88 KB
English
-
MYR 0.00
-
http://arxiv.org/abs/1508.07603
Share this eBook