{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T06:43:41Z","timestamp":1740120221343,"version":"3.37.3"},"reference-count":32,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1156701"],"award-info":[{"award-number":["DMS-1156701"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-0917676"],"award-info":[{"award-number":["IIS-0917676"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:p> We study a turn-based game in a simply connected polygonal environment [Formula: see text] between a pursuer [Formula: see text] and an adversarial evader [Formula: see text]. Both players can move in a straight line to any point within unit distance during their turn. The pursuer [Formula: see text] wins by capturing the evader, meaning that their distance satisfies [Formula: see text], while the evader wins by eluding capture forever. Both players have a map of the environment, but they have different sensing capabilities. The evader [Formula: see text] always knows the location of [Formula: see text]. Meanwhile, [Formula: see text] only has line-of-sight visibility: [Formula: see text] observes the evader\u2019s position only when the line segment connecting them lies entirely within the polygon. Therefore [Formula: see text] must search for [Formula: see text] when the evader is hidden from view. <\/jats:p><jats:p> We provide a winning strategy for [Formula: see text] in two families of polygons: monotone polygons and scallop polygons. In both families, a straight line [Formula: see text] can be moved continuously over [Formula: see text] so that (1) [Formula: see text] is a line segment and (2) every point on the boundary [Formula: see text] 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\u2019s strategy during its pursuit phase, rather than the well-known lion\u2019s strategy. The rook\u2019s strategy is crucial for obtaining a capture time that is linear in the area of [Formula: see text]. For both monotone and scallop polygons, our algorithm has a capture time of [Formula: see text], where [Formula: see text] is the number of polygon vertices. <\/jats:p>","DOI":"10.1142\/s0218195919500122","type":"journal-article","created":{"date-parts":[[2020,5,6]],"date-time":"2020-05-06T06:07:05Z","timestamp":1588745225000},"page":"307-351","source":"Crossref","is-referenced-by-count":1,"title":["Line-of-Sight Pursuit in Monotone and Scallop Polygons"],"prefix":"10.1142","volume":"29","author":[{"given":"Lindsay","family":"Berry","sequence":"first","affiliation":[{"name":"Statistical Science Department, Duke University, Durham, NC 27708, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9823-2867","authenticated-orcid":false,"given":"Andrew","family":"Beveridge","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Statistics, and Computer Science, Macalester College, St. Paul, MN 55105, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3960-9617","authenticated-orcid":false,"given":"Jane","family":"Butterfield","sequence":"additional","affiliation":[{"name":"Department of Mathematics & Statistics, University of Victoria, Victoria, BC V8X 2X6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0868-5441","authenticated-orcid":false,"given":"Volkan","family":"Isler","sequence":"additional","affiliation":[{"name":"Department of Computer Science & Engineering, University of Minnesota, Minneapolis, MN 55455, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6337-4339","authenticated-orcid":false,"given":"Zachary","family":"Keller","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Minnesota, Minneapolis, MN 55455, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alana","family":"Shine","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Southern California, Los Angeles, CA 90089, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junyi","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Statistics, and Computer Science, Macalester College, St. Paul, MN 55105, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2020,5,6]]},"reference":[{"key":"S0218195919500122BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90073-8"},{"volume-title":"Proc. Robotics: Science and Systems","author":"Alexander S.","key":"S0218195919500122BIB002"},{"key":"S0218195919500122BIB003","doi-asserted-by":"publisher","DOI":"10.4171\/LEM\/55-1-5"},{"key":"S0218195919500122BIB004","doi-asserted-by":"publisher","DOI":"10.26493\/1855-3974.1060.031"},{"key":"S0218195919500122BIB005","doi-asserted-by":"publisher","DOI":"10.1177\/0278364912452894"},{"key":"S0218195919500122BIB006","doi-asserted-by":"publisher","DOI":"10.1090\/stml\/061"},{"key":"S0218195919500122BIB007","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2007.4282476"},{"key":"S0218195919500122BIB008","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195905001877"},{"key":"S0218195919500122BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-011-9241-4"},{"key":"S0218195919500122BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/BF01901192"},{"key":"S0218195919500122BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/BF01901482"},{"key":"S0218195919500122BIB012","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000273"},{"key":"S0218195919500122BIB013","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"Hefferman P. J.","year":"1987","journal-title":"Algorithmica"},{"key":"S0218195919500122BIB014","doi-asserted-by":"publisher","DOI":"10.1145\/109648.109667"},{"issue":"21","key":"S0218195919500122BIB015","first-page":"864","volume":"5","author":"Isler V.","year":"2005","journal-title":"IEEE Trans. Robotics"},{"key":"S0218195919500122BIB016","first-page":"359","volume":"2","author":"Jankovic V.","year":"1978","journal-title":"Matematicki Vesnik"},{"key":"S0218195919500122BIB017","first-page":"2010","volume-title":"Proc. of 26th Conf. on Artificial Intelligence","author":"Klein K.","year":"2012"},{"key":"S0218195919500122BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2014.10.002"},{"key":"S0218195919500122BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.04.012"},{"key":"S0218195919500122BIB020","doi-asserted-by":"publisher","DOI":"10.1145\/322139.322142"},{"volume-title":"Littlewood\u2019s Miscellany","year":"1986","author":"Littlewood J. E.","key":"S0218195919500122BIB021"},{"volume-title":"Workshop on the Algorithmic Foundations of Robotics (WAFR)","year":"2014","author":"Noori N.","key":"S0218195919500122BIB022"},{"key":"S0218195919500122BIB023","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2014.6942794"},{"key":"S0218195919500122BIB024","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913498291"},{"key":"S0218195919500122BIB025","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90160-7"},{"key":"S0218195919500122BIB026","first-page":"787","volume-title":"The Handbook of Computational Geometry","author":"O\u2019Rourke J.","year":"2018","edition":"3"},{"key":"S0218195919500122BIB027","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0070400"},{"key":"S0218195919500122BIB028","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90091-0"},{"key":"S0218195919500122BIB030","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00411-4"},{"volume-title":"2014 IEEE Int. Conf. Robotics and Automation (ICRA)","author":"Stiffler N.","key":"S0218195919500122BIB031"},{"key":"S0218195919500122BIB032","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68405-3_30"},{"key":"S0218195919500122BIB033","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195998000060"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195919500122","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,6]],"date-time":"2020-05-06T06:07:14Z","timestamp":1588745234000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195919500122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12]]},"references-count":32,"journal-issue":{"issue":"04","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["10.1142\/S0218195919500122"],"URL":"https:\/\/doi.org\/10.1142\/s0218195919500122","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"type":"print","value":"0218-1959"},{"type":"electronic","value":"1793-6357"}],"subject":[],"published":{"date-parts":[[2019,12]]}}}