Escaping a Polygon
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908603191918592 |
|---|---|
| author | Abel, Zachary Akitaya, Hugo Demaine, Erik D. Demaine, Martin L. Hesterberg, Adam Ku, Jason S. Lynch, Jayson |
| author_facet | Abel, Zachary Akitaya, Hugo Demaine, Erik D. Demaine, Martin L. Hesterberg, Adam Ku, Jason S. Lynch, Jayson |
| contents | Suppose an escaping player ("human") moves continuously at maximum speed $1$ in the interior of a region, while a pursuing player ("zombie") moves continuously at maximum speed $r$ outside the region. For what $r$ can the first player escape the region, that is, reach the boundary a positive distance away from the pursuing player, assuming optimal play by both players? We formalize a model for this infinitesimally alternating 2-player game and prove that it has a unique winner in any locally rectifiable region. Our model thus avoids pathological behaviors (where both players can have "winning strategies") previously identified for pursuit-evasion games such as the Lion and Man problem in certain metric spaces. For some specific regions, including both equilateral triangle and square, we give exact results for the critical speed ratio, above which the pursuing player can win and below which the escaping player can win (and at which the pursuing player can win). For simple polygons, we give a simple formula and polynomial-time algorithm that is guaranteed to give a 10.89898-approximation to the critical speed ratio, and we give a pseudopolynomial-time approximation scheme for approximating the critical speed ratio arbitrarily closely. On the negative side, we prove NP-hardness of the problem for polyhedral domains in 3D, and prove stronger results (PSPACE-hardness and NP-hardness even to approximate) for generalizations to multiple escaping and pursuing players. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2007_08965 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Escaping a Polygon Abel, Zachary Akitaya, Hugo Demaine, Erik D. Demaine, Martin L. Hesterberg, Adam Ku, Jason S. Lynch, Jayson Computational Geometry Computer Science and Game Theory Metric Geometry Suppose an escaping player ("human") moves continuously at maximum speed $1$ in the interior of a region, while a pursuing player ("zombie") moves continuously at maximum speed $r$ outside the region. For what $r$ can the first player escape the region, that is, reach the boundary a positive distance away from the pursuing player, assuming optimal play by both players? We formalize a model for this infinitesimally alternating 2-player game and prove that it has a unique winner in any locally rectifiable region. Our model thus avoids pathological behaviors (where both players can have "winning strategies") previously identified for pursuit-evasion games such as the Lion and Man problem in certain metric spaces. For some specific regions, including both equilateral triangle and square, we give exact results for the critical speed ratio, above which the pursuing player can win and below which the escaping player can win (and at which the pursuing player can win). For simple polygons, we give a simple formula and polynomial-time algorithm that is guaranteed to give a 10.89898-approximation to the critical speed ratio, and we give a pseudopolynomial-time approximation scheme for approximating the critical speed ratio arbitrarily closely. On the negative side, we prove NP-hardness of the problem for polyhedral domains in 3D, and prove stronger results (PSPACE-hardness and NP-hardness even to approximate) for generalizations to multiple escaping and pursuing players. |
| title | Escaping a Polygon |
| topic | Computational Geometry Computer Science and Game Theory Metric Geometry |
| url | https://arxiv.org/abs/2007.08965 |