{"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":1740120221767,"version":"3.37.3"},"reference-count":25,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2020,3]]},"abstract":"<jats:p> We study the shortest [Formula: see text]-violation path problem in a simple polygon. Let [Formula: see text] be a simple polygon in [Formula: see text] with [Formula: see text] vertices and let [Formula: see text] be a pair of points in [Formula: see text]. Let [Formula: see text] represent the interior of [Formula: see text]. Let [Formula: see text] represent the exterior of [Formula: see text]. For an integer [Formula: see text], the shortest [Formula: see text]-violation path problem in [Formula: see text] is the problem of computing the shortest path from [Formula: see text] to [Formula: see text] in [Formula: see text], such that at most [Formula: see text] path segments are allowed to be in [Formula: see text]. The subpaths of a [Formula: see text]-violation path are not allowed to bend in [Formula: see text]. For any [Formula: see text], we present a [Formula: see text] factor approximation algorithm for the problem that runs in [Formula: see text] time. Here [Formula: see text] and [Formula: see text], [Formula: see text], [Formula: see text] are geometric parameters. <\/jats:p>","DOI":"10.1142\/s0218195920500041","type":"journal-article","created":{"date-parts":[[2020,9,2]],"date-time":"2020-09-02T09:52:10Z","timestamp":1599040330000},"page":"79-95","source":"Crossref","is-referenced-by-count":0,"title":["Approximate Shortest Paths in Polygons with Violations"],"prefix":"10.1142","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3151-8454","authenticated-orcid":false,"given":"Binayak","family":"Dutta","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Tezpur University, Tezpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sasanka","family":"Roy","sequence":"additional","affiliation":[{"name":"Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2020,8,31]]},"reference":[{"volume-title":"16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)","year":"2018","author":"Agarwal P. K.","key":"S0218195920500041BIB001"},{"key":"S0218195920500041BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0054351"},{"key":"S0218195920500041BIB003","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.65"},{"key":"S0218195920500041BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574703"},{"key":"S0218195920500041BIB005","doi-asserted-by":"publisher","DOI":"10.1137\/130913808"},{"key":"S0218195920500041BIB006","doi-asserted-by":"publisher","DOI":"10.1137\/06067777X"},{"key":"S0218195920500041BIB007","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511543340"},{"key":"S0218195920500041BIB008","doi-asserted-by":"publisher","DOI":"10.1137\/0220055"},{"key":"S0218195920500041BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840360"},{"volume-title":"25th Annual European Symposium on Algorithms (ESA 2017)","year":"2017","author":"Hershberger J.","key":"S0218195920500041BIB010"},{"key":"S0218195920500041BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(97)00004-7"},{"key":"S0218195920500041BIB012","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289604"},{"key":"S0218195920500041BIB013","doi-asserted-by":"publisher","DOI":"10.1145\/73393.73411"},{"key":"S0218195920500041BIB014","doi-asserted-by":"publisher","DOI":"10.1145\/262839.262984"},{"key":"S0218195920500041BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-2256-2_1"},{"key":"S0218195920500041BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0263-3"},{"key":"S0218195920500041BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530888"},{"key":"S0218195920500041BIB018","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195996000216"},{"key":"S0218195920500041BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50016-4"},{"key":"S0218195920500041BIB020","doi-asserted-by":"publisher","DOI":"10.1145\/73393.73410"},{"key":"S0218195920500041BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90045-1"},{"volume-title":"Comput. Geom. Theory Appl.","year":"1990","author":"Snoeyink J. H. J.","key":"S0218195920500041BIB023"},{"key":"S0218195920500041BIB024","doi-asserted-by":"publisher","DOI":"10.1145\/185675.185795"},{"key":"S0218195920500041BIB025","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45678-3_15"},{"volume-title":"Proceedings of the 11th Canadian Conference on Computational Geometry","year":"1999","author":"Toussaint G. T.","key":"S0218195920500041BIB026"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195920500041","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,2]],"date-time":"2020-09-02T09:52:22Z","timestamp":1599040342000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195920500041"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3]]},"references-count":25,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["10.1142\/S0218195920500041"],"URL":"https:\/\/doi.org\/10.1142\/s0218195920500041","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"type":"print","value":"0218-1959"},{"type":"electronic","value":"1793-6357"}],"subject":[],"published":{"date-parts":[[2020,3]]}}}