{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:58:11Z","timestamp":1760237891431,"version":"build-2065373602"},"reference-count":21,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2020,6,23]],"date-time":"2020-06-23T00:00:00Z","timestamp":1592870400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The Evasion Problem is the question of whether\u2014given a collection of sensors and a particular movement pattern over time\u2014it is possible to stay undetected within the domain over the same stretch of time. It has been studied using topological techniques since 2006\u2014with sufficient conditions for non-existence of an Evasion Path provided by de Silva and Ghrist; sufficient and necessary conditions with extended sensor capabilities provided by Adams and Carlsson; and sufficient and necessary conditions using sheaf theory by Krishnan and Ghrist. In this paper, we propose three algorithms for the Evasion Problem: one distributed algorithm extension of Adams\u2019 approach for evasion path detection, and two different approaches to evasion path enumeration.<\/jats:p>","DOI":"10.3390\/a13060149","type":"journal-article","created":{"date-parts":[[2020,6,23]],"date-time":"2020-06-23T06:11:02Z","timestamp":1592892662000},"page":"149","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Distributed Approach to the Evasion Problem"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3755-9804","authenticated-orcid":false,"given":"Denis","family":"Khryashchev","sequence":"first","affiliation":[{"name":"Computer Science, CUNY Graduate Center, 365 5th Ave, New York, NY 10016, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1071-9292","authenticated-orcid":false,"given":"Jie","family":"Chu","sequence":"additional","affiliation":[{"name":"Computer Science, CUNY Graduate Center, 365 5th Ave, New York, NY 10016, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6322-7542","authenticated-orcid":false,"given":"Mikael","family":"Vejdemo-Johansson","sequence":"additional","affiliation":[{"name":"Computer Science, CUNY Graduate Center, 365 5th Ave, New York, NY 10016, USA"},{"name":"Mathematics, CUNY College of Staten Island, 2800 Victory Blvd, Staten Island, NY 10314, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ping","family":"Ji","sequence":"additional","affiliation":[{"name":"Computer Science, CUNY Graduate Center, 365 5th Ave, New York, NY 10016, USA"},{"name":"Mathematics and Computer Science, CUNY John Jay College, 524 W 59th St, New York, NY 10019, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,6,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1205","DOI":"10.1177\/0278364906072252","article-title":"Coordinate-Free Coverage in Sensor Networks with Controlled Boundaries via Homology","volume":"25","author":"Ghrist","year":"2006","journal-title":"Int. J. Robot. Res."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1177\/0278364914548051","article-title":"Evasion paths in mobile sensor networks","volume":"34","author":"Adams","year":"2015","journal-title":"Int. J. Robot. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1137\/16M1089083","article-title":"Positive Alexander Duality for Pursuit and Evasion","volume":"1","author":"Ghrist","year":"2017","journal-title":"SIAM J. Appl. Algebra Geom."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1016\/j.jnca.2011.11.016","article-title":"A survey on coverage and connectivity issues in wireless sensor networks","volume":"35","author":"Zhu","year":"2012","journal-title":"J. Netw. Comput. Appl."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/j.comcom.2017.06.010","article-title":"Coverage in Mobile Wireless Sensor Networks (M-WSN)","volume":"110","author":"Mohamed","year":"2017","journal-title":"Comput. Commun."},{"key":"ref_6","first-page":"89","article-title":"Maintaining sensing coverage and connectivity in large sensor networks","volume":"1","author":"Zhang","year":"2005","journal-title":"Ad Hoc Sens. Wirel. Netw."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1007\/s11036-005-1564-y","article-title":"The Coverage Problem in a Wireless Sensor Network","volume":"10","author":"Huang","year":"2005","journal-title":"Mob. Netw. Appl."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Wang, X., Xing, G., Zhang, Y., Lu, C., Pless, R., and Gill, C. (2003, January 5\u20137). Integrated coverage and connectivity configuration in wireless sensor networks. Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, Los Angeles, CA, USA.","DOI":"10.1145\/958491.958496"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Garg, V., Wattenhofer, R., and Kothapalli, K. (2009). Q-Coverage Problem in Wireless Sensor Networks. Distributed Computing and Networking, Springer.","DOI":"10.1007\/978-3-540-92295-7"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"876","DOI":"10.1109\/JSEN.2014.2310180","article-title":"A Survey on Barrier Coverage Problem in Directional Sensor Networks","volume":"15","author":"Tao","year":"2015","journal-title":"IEEE Sens. J."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1534","DOI":"10.1109\/TMC.2010.237","article-title":"Sweep Coverage with Mobile Sensors","volume":"10","author":"Li","year":"2011","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"339","DOI":"10.2140\/agt.2007.7.339","article-title":"Coverage in Sensor Networks via Persistent Homology","volume":"7","author":"Ghrist","year":"2007","journal-title":"Algebr. Geomet. Topol."},{"key":"ref_13","first-page":"10","article-title":"Homological Sensor Networks","volume":"54","author":"Ghrist","year":"2007","journal-title":"Not. Am. Math. Soc."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/s00200-012-0167-7","article-title":"Distributed computation of coverage in sensor networks by homological methods","volume":"23","author":"Ghrist","year":"2012","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Gamble, J., Chintakunta, H., and Krim, H. (2012, January 22\u201325). Applied Topology in Static and Dynamic Sensor Networks. Proceedings of the International Conference on Signal Processing and Communications (SPCOM), Bangalore, India.","DOI":"10.1109\/SPCOM.2012.6290237"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"2493","DOI":"10.1109\/COMST.2015.2407954","article-title":"Movement-Assisted Sensor Deployment Algorithms: A Survey and Taxonomy","volume":"17","author":"Senouci","year":"2015","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1267","DOI":"10.1109\/TPDS.2013.137","article-title":"Localized Movement-Assisted SensorDeployment Algorithm for HoleDetection and Healing","volume":"25","author":"Senouci","year":"2014","journal-title":"IEEE Trans. Parallel. Distr. Syst."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Alsalih, W., Islam, K., N\u00fa\u00f1ez Rodr\u00edguez, Y., and Xiao, H. (2008, January 14\u201316). Distributed Voronoi Diagram Computation in Wireless Sensor Networks. Proceedings of the Twentieth Annual Symposium on Parallelism in Algorithms and Architectures, New York, NY, USA.","DOI":"10.1145\/1378533.1378597"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Karp, B., and Kung, H.T. (2000, January 1). GPSR: Greedy perimeter stateless routing for wireless networks. Proceedings of the 6th annual international conference on Mobile computing and networking, Boston, MA, USA.","DOI":"10.1145\/345910.345953"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0925-7721(94)90018-3","article-title":"A linear-time construction of the relative neighborhood graph from the Delaunay triangulation","volume":"4","author":"Lingas","year":"1994","journal-title":"Comput. Geom."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H. (2001). Geometry and Topology for Mesh Generation, Cambridge University Press.","DOI":"10.1017\/CBO9780511530067"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/6\/149\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:41:36Z","timestamp":1760175696000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/6\/149"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,23]]},"references-count":21,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2020,6]]}},"alternative-id":["a13060149"],"URL":"https:\/\/doi.org\/10.3390\/a13060149","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,6,23]]}}}