{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:58Z","timestamp":1740122398684,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,1,13]],"date-time":"2020-01-13T00:00:00Z","timestamp":1578873600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,13]],"date-time":"2020-01-13T00:00:00Z","timestamp":1578873600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100005276","name":"National Board for Higher Mathematics","doi-asserted-by":"publisher","award":["248(17)2014-R&D-II\/1049"],"award-info":[{"award-number":["248(17)2014-R&D-II\/1049"]}],"id":[{"id":"10.13039\/501100005276","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001843","name":"Science and Engineering Research Board","doi-asserted-by":"publisher","award":["MATRICS grant MTR\/2017\/000474"],"award-info":[{"award-number":["MATRICS grant MTR\/2017\/000474"]}],"id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s10878-020-00524-0","type":"journal-article","created":{"date-parts":[[2020,1,13]],"date-time":"2020-01-13T17:02:43Z","timestamp":1578934963000},"page":"1594-1614","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Computing an $$L_1$$ shortest path among splinegonal obstacles in the plane"],"prefix":"10.1007","volume":"44","author":[{"given":"Tameem","family":"Choudhury","sequence":"first","affiliation":[]},{"given":"R.","family":"Inkulu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,1,13]]},"reference":[{"key":"524_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal PK, Sharathkumar R, Yu H (2009) Approximate Euclidean shortest paths amid convex obstacles. In: Proceedings of symposium on discrete algorithms, pp 283\u2013292","DOI":"10.1137\/1.9781611973068.32"},{"key":"524_CR2","doi-asserted-by":"crossref","unstructured":"Arikati SR, Chen DZ, Chew LP, Das G, Smid MHM, Zaroliagis CD (1996) Planar spanners and approximate shortest path queries among obstacles in the plane. In: Proceedings of European symposium on algorithms, pp 514\u2013528","DOI":"10.1007\/3-540-61680-2_79"},{"issue":"6","key":"524_CR3","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/0925-7721(93)90004-P","volume":"3","author":"M Atallah","year":"1993","unstructured":"Atallah M, Chen DZ (1993) On parallel rectilinear obstacle-avoiding paths. Comput Geom 3(6):307\u2013313","journal-title":"Comput Geom"},{"issue":"4","key":"524_CR4","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1142\/S0218195994000252","volume":"4","author":"R Bar-Yehuda","year":"1994","unstructured":"Bar-Yehuda R, Chazelle B (1994) Triangulating disjoint Jordan chains. Int J Comput Geom Appl 4(4):475\u2013481","journal-title":"Int J Comput Geom Appl"},{"issue":"6","key":"524_CR5","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/0020-0190(96)00020-8","volume":"57","author":"DZ Chen","year":"1996","unstructured":"Chen DZ, Klenk KS (1996) Rectilinear short path queries among rectangular obstacles. Inf Process Lett 57(6):313\u2013319","journal-title":"Inf Process Lett"},{"key":"524_CR6","doi-asserted-by":"crossref","unstructured":"Chen DZ, Wang H (2011) A nearly optimal algorithm for finding $L_1$ shortest paths among polygoal obstacles in the plane. In: Proceedings of European symposium on algorithms, pp 481\u2013492","DOI":"10.1007\/978-3-642-23719-5_41"},{"issue":"4","key":"524_CR7","doi-asserted-by":"publisher","first-page":"26:1","DOI":"10.1145\/2660771","volume":"11","author":"DZ Chen","year":"2015","unstructured":"Chen DZ, Wang H (2015) Computing shortest paths among curved obstacles in the plane. ACM Trans Algorithms 11(4):26:1\u201326:46","journal-title":"ACM Trans Algorithms"},{"issue":"1","key":"524_CR8","first-page":"473","volume":"7","author":"DZ Chen","year":"2016","unstructured":"Chen DZ, Inkulu R, Wang H (2016) Two-point $L_1$ shortest path queries in the plane. J Comput Geom 7(1):473\u2013519","journal-title":"J Comput Geom"},{"key":"524_CR9","unstructured":"Clarkson KL, Kapoor S, Vaidya PM (1987) Rectilinear shortest paths through polygonal obstacles in $O(n(\\lg {n})^2)$ time. In: Proceedings of symposium on computational geometry, pp 251\u2013257"},{"key":"524_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational geometry: algorithms and applications","author":"M de Berg","year":"2008","unstructured":"de Berg M, Cheong O, van Kreveld M, Overmars M (2008) Computational geometry: algorithms and applications, 3rd edn. Springer, Berlin","edition":"3"},{"key":"524_CR11","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02187714","volume":"4","author":"PJ de Rezende","year":"1989","unstructured":"de Rezende PJ, Lee DT, Wu Y-F (1989) Rectilinear shortest paths in the presence of rectangular barriers. Discrete Comput Geom 4:41\u201353","journal-title":"Discrete Comput Geom"},{"issue":"3","key":"524_CR12","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/BF01840397","volume":"5","author":"DP Dobkin","year":"1990","unstructured":"Dobkin DP, Souvaine DL (1990) Computational geometry in a curved world. Algorithmica 5(3):421\u2013457","journal-title":"Algorithmica"},{"key":"524_CR13","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/BF01762127","volume":"3","author":"DP Dobkin","year":"1988","unstructured":"Dobkin DP, Souvaine DL, Van Wyk CJ (1988) Decomposition and intersection of simple splinegons. Algorithmica 3:473\u2013485","journal-title":"Algorithmica"},{"issue":"1","key":"524_CR14","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1142\/S0218195994000021","volume":"4","author":"HA ElGindy","year":"1994","unstructured":"ElGindy HA, Mitra P (1994) Orthogonal shortest route queries among axis parallel rectangular obstacles. Int J Comput Geom Appl 4(1):3\u201324","journal-title":"Int J Comput Geom Appl"},{"key":"524_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511543340","volume-title":"Visibility algorithms in the plane","author":"SK Ghosh","year":"2007","unstructured":"Ghosh SK (2007) Visibility algorithms in the plane. Cambridge University Press, New York"},{"issue":"5","key":"524_CR16","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1137\/0220055","volume":"20","author":"SK Ghosh","year":"1991","unstructured":"Ghosh SK, Mount DM (1991) An output-sensitive algorithm for computing visibility graphs. SIAM J Comput 20(5):888\u2013910","journal-title":"SIAM J Comput"},{"issue":"2","key":"524_CR17","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/0022-0000(89)90041-X","volume":"39","author":"LJ Guibas","year":"1989","unstructured":"Guibas LJ, Hershberger J (1989) Optimal shortest path queries in a simple polygon. J Comput Syst Sci 39(2):126\u2013152","journal-title":"J Comput Syst Sci"},{"issue":"5","key":"524_CR18","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0020-0190(91)90064-O","volume":"38","author":"J Hershberger","year":"1991","unstructured":"Hershberger J (1991) A new data structure for shortest path queries in a simple polygon. Inf Process Lett 38(5):231\u2013235","journal-title":"Inf Process Lett"},{"issue":"2","key":"524_CR19","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0925-7721(94)90010-8","volume":"4","author":"J Hershberger","year":"1994","unstructured":"Hershberger J, Snoeyink J (1994) Computing minimum length paths of a given homotopy class. Comput Geom 4(2):63\u201397","journal-title":"Comput Geom"},{"issue":"6","key":"524_CR20","doi-asserted-by":"publisher","first-page":"2215","DOI":"10.1137\/S0097539795289604","volume":"28","author":"J Hershberger","year":"1999","unstructured":"Hershberger J, Suri S (1999) An optimal algorithm for Euclidean shortest paths in the plane. SIAM J Comput 28(6):2215\u20132256","journal-title":"SIAM J Comput"},{"key":"524_CR21","doi-asserted-by":"crossref","unstructured":"Hershberger J, Suri S, Yildiz H (2012) A near-optimal algorithm for shortest paths among curved obstacles in the plane. In: Proceedings of symposuim on computational geometry, pp 359\u2013368","DOI":"10.1145\/2462356.2462374"},{"issue":"9","key":"524_CR22","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1016\/j.comgeo.2009.02.005","volume":"42","author":"R Inkulu","year":"2009","unstructured":"Inkulu R, Kapoor S (2009) Planar rectilinear shortest path computation using corridors. Comput Geom 42(9):873\u2013884","journal-title":"Comput Geom"},{"key":"524_CR23","unstructured":"Inkulu R, Kapoor S (2019) Approximate Euclidean shortest paths amid polygonal obstacles. In: Proceedings of symposium on algorithms and computation"},{"key":"524_CR24","unstructured":"Inkulu R, Kapoor S, Maheshwari SN (2010) A near optimal algorithm for finding Euclidean shortest path in polygonal domain. CoRR, arXiv:1011.6481"},{"issue":"3","key":"524_CR25","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1137\/S0097539795253591","volume":"30","author":"S Kapoor","year":"2000","unstructured":"Kapoor S, Maheshwari SN (2000) Efficiently constructing the visibility graph of a simple polygon with obstacles. SIAM J Comput 30(3):847\u2013871","journal-title":"SIAM J Comput"},{"issue":"4","key":"524_CR26","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/PL00009323","volume":"18","author":"S Kapoor","year":"1997","unstructured":"Kapoor S, Maheshwari SN, Mitchell JSB (1997) An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane. Discrete Comput Geom 18(4):377\u2013383","journal-title":"Discrete Comput Geom"},{"key":"524_CR27","unstructured":"Kapoor S, Maheshwari SN (1998) Efficent algorithms for Euclidean shortest path and visibility problems with polygonal obstacles. In: Proceedings of symposium on computational geometry, pp 172\u2013182"},{"issue":"4","key":"524_CR28","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1137\/0221038","volume":"21","author":"EA Melissaratos","year":"1992","unstructured":"Melissaratos EA, Souvaine DL (1992) Shortest paths help solve geometric optimization problems in planar regions. SIAM J Comput 21(4):601\u2013638","journal-title":"SIAM J Comput"},{"key":"524_CR29","unstructured":"Mitchell JSB (1989) An optimal algorithm for shortest rectilinear paths among obstacles. In: Canadian conference on computational geometry, p 22"},{"issue":"1","key":"524_CR30","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF01758836","volume":"8","author":"JSB Mitchell","year":"1992","unstructured":"Mitchell JSB (1992) $L_1$ shortest paths among polygonal obstacles in the plane. Algorithmica 8(1):55\u201388","journal-title":"Algorithmica"},{"issue":"3","key":"524_CR31","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1142\/S0218195996000216","volume":"6","author":"JSB Mitchell","year":"1996","unstructured":"Mitchell JSB (1996) Shortest paths among obstacles in the plane. Int J Comput Geom Appl 6(3):309\u2013332","journal-title":"Int J Comput Geom Appl"},{"key":"524_CR32","doi-asserted-by":"crossref","unstructured":"Mitra BK, Bhattacharya P (1993) Efficient approximate shortest-path queries among isothetic rectangular obstacles. In: Proceedings of the third workshop on algorithms and data structures, pp 518\u2013529","DOI":"10.1007\/3-540-57155-8_276"},{"issue":"2","key":"524_CR33","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0020-0190(86)90045-1","volume":"23","author":"H Rohnert","year":"1986","unstructured":"Rohnert H (1986) Shortest paths in the plane with convex polygonal obstacles. Inf Process Lett 23(2):71\u201376","journal-title":"Inf Process Lett"},{"issue":"5","key":"524_CR34","doi-asserted-by":"publisher","first-page":"982","DOI":"10.1145\/185675.185795","volume":"41","author":"JA Storer","year":"1994","unstructured":"Storer JA, Reif JH (1994) Shortest paths in the plane with polygonal obstacles. J ACM 41(5):982\u20131012","journal-title":"J ACM"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00524-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00524-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00524-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T08:44:47Z","timestamp":1664354687000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00524-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,13]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["524"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00524-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,1,13]]},"assertion":[{"value":"13 January 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}