{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T15:11:31Z","timestamp":1723043491783},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2015,6]]},"abstract":"<jats:p> We study pursuit-evasion in a polygonal environment with polygonal obstacles. In this turn based game, an evader [Formula: see text] is chased by pursuers [Formula: see text]. The players have full information about the environment and the location of the other players. The pursuers are allowed to coordinate their actions. On the pursuer turn, each [Formula: see text] can move to any point at distance at most 1 from his current location. On the evader turn, he moves similarly. The pursuers win if some pursuer becomes co-located with the evader in finite time. The evader wins if he can evade capture forever. <\/jats:p><jats:p> It is known that one pursuer can capture the evader in any simply-connected polygonal environment, and that three pursuers are always sufficient in any polygonal environment [Formula: see text] (possibly with polygonal obstacles). We contribute two new results to this field. First, we fully characterize when an environment with a single obstacle is one-pursuerwin or two-pursuer-win. Second, we give sufficient (but not necessary) conditions for an environment to have a winning strategy for two pursuers. Such environments can be swept by a leapfrog strategy in which the two cops alternately guard\/increase the currently controlled area. The running time of this algorithm is [Formula: see text] where [Formula: see text] is the number of vertices, [Formula: see text] is the number of obstacles and [Formula: see text] is the diameter of the polygonal environment [Formula: see text]. <\/jats:p><jats:p> More concretely, for an environment with [Formula: see text] vertices, we describe an [Formula: see text] algorithm that (1) determines whether the obstacles are well-separated, and if so, (2) constructs the required partition for a leapfrog strategy. <\/jats:p>","DOI":"10.1142\/s0218195915500065","type":"journal-article","created":{"date-parts":[[2015,7,21]],"date-time":"2015-07-21T02:06:51Z","timestamp":1437444411000},"page":"77-100","source":"Crossref","is-referenced-by-count":9,"title":["A Leapfrog Strategy for Pursuit-Evasion in a Polygonal Environment"],"prefix":"10.1142","volume":"25","author":[{"given":"Brendan","family":"Ames","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Alabama, Box 870350, Tuscaloosa, AL 35487, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Beveridge","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Statistics and Computer Science, Macalester College, 1600 Grand Avenue, St Paul, MN 55105, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rosalie","family":"Carlson","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of California, South Hall, Room 6607, Santa Barbara, CA 93106, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Claire","family":"Djang","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Oberlin College, 10 N. Professor St, King 205, Oberlin, OH 44074, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Volkan","family":"Isler","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Minnesota, 4-192 Keller Hall, 200 Union St SE, Minneapolis, MN 55455, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen","family":"Ragain","sequence":"additional","affiliation":[{"name":"Department of Management Science and Engineering, Stanford University, Huang Engineering Center, 475 Via Ortega, Stanford, CA 94305, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maxray","family":"Savage","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Statistics and Computer Science, Macalester College, 1600 Grand Avenue, St Paul, MN 55105, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2015,7,20]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-011-9241-4"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.4.4.447"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00411-4"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.04.012"},{"issue":"21","key":"p_6","first-page":"864","volume":"5","author":"Isler V.","year":"2005","journal-title":"IEEE Trans. Rob."},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1177\/0278364912452894"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90073-8"},{"key":"p_9","first-page":"5","volume":"59","author":"Alspach B.","year":"2006","journal-title":"Mathematiche"},{"key":"p_10","first-page":"163","volume":"36","author":"Hahn G.","year":"2007","journal-title":"Tatra Mt Math. Pub."},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000273"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480104442169"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195905001877"},{"key":"p_15","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1090\/qam\/253822","volume":"27","author":"Yen J. Y.","year":"1970","journal-title":"Q. Appl. Math."}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195915500065","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T23:48:53Z","timestamp":1565135333000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195915500065"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6]]},"references-count":13,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2015,7,20]]},"published-print":{"date-parts":[[2015,6]]}},"alternative-id":["10.1142\/S0218195915500065"],"URL":"https:\/\/doi.org\/10.1142\/s0218195915500065","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6]]}}}