Loading...
Please wait, while we are loading the content...
Similar Documents
Capture bounds for visibility-based pursuit evasion (2013)
| Content Provider | CiteSeerX |
|---|---|
| Author | Klein, Kyle Suri, Subhash |
| Description | We investigate the following problem in the visibility-based discrete-time model of pursuit evasion in the plane: how many pursuers are needed to capture an evader in a polygonal environment with obstacles under the minimalist assumption that pursuers and the evader have the same maximum speed? When the environment is a simply-connected (hole-free) polygon of n vertices, we show that Θ(n1/2) pursuers are both necessary and sufficient in the worst-case. When the environment is a polygon with holes, we prove a lower bound of Ω(n2/3) and an upper bound of O(n5/6) for the number of pursuers that are needed in the worst-case, where n is the total number of vertices including the hole boundaries. More precisely, if the polygon contains h holes, our upper bound is O(n1/2h1/4), for h ≤ n2/3, and O(n1/3h1/2) otherwise. We then show with additional assumptions these bounds can be drastically improved. Namely, if the players ’ movement speed is small compared to the “features ” of the environment, we give a deterministic algorithm with a worst case upper bound of O(log n) pursuers for simply-connected n-gons and O( h+log n) for multiply-connected polygons with h holes. Further, if the pursuers are allowed to randomize their strategy, regardless of the players ’ movement speed, we show that O(1) pursuers can capture the evader in a simply connected n-gon and O( h) when there are h holes with high probability. |
| File Format | |
| Language | English |
| Publisher | ACM |
| Publisher Date | 2013-01-01 |
| Publisher Institution | In Proc. of the 29th Symposium on Computational Geometry, SoCG ’13 |
| Access Restriction | Open |
| Subject Keyword | Visibility-based Pursuit Evasion Hole Boundary Many Pursuer Polygonal Environment Additional Assumption Pursuit Evasion Minimalist Assumption Maximum Speed Simply-connected N-gons Total Number Worst Case Upper Bound Player Movement Speed Multiply-connected Polygon Deterministic Algorithm Upper Bound Visibility-based Discrete-time Model High Probability |
| Content Type | Text |
| Resource Type | Article |
