{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,30]],"date-time":"2024-03-30T19:05:35Z","timestamp":1711825535406},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,7,7]],"date-time":"2020-07-07T00:00:00Z","timestamp":1594080000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,7]],"date-time":"2020-07-07T00:00:00Z","timestamp":1594080000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,7]]},"DOI":"10.1007\/s10878-020-00604-1","type":"journal-article","created":{"date-parts":[[2020,7,7]],"date-time":"2020-07-07T07:04:41Z","timestamp":1594105481000},"page":"1036-1074","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Shortest paths among transient obstacles"],"prefix":"10.1007","volume":"43","author":[{"given":"Anil","family":"Maheshwari","sequence":"first","affiliation":[]},{"given":"Arash","family":"Nouri","sequence":"additional","affiliation":[]},{"given":"J\u00f6rg-R\u00fcdiger","family":"Sack","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,7,7]]},"reference":[{"key":"604_CR1","unstructured":"Agarwal PK, Arge L, Yi K (2005) An optimal dynamic interval stabbing-max data structure? In: Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA \u201905. Society for Industrial and Applied Mathematics, Philadelphia, pp 803\u2013812. http:\/\/dl.acm.org\/citation.cfm?id=1070432.1070546"},{"key":"604_CR2","unstructured":"Agarwal PK, Kumar N, Sintos S, Suri S (2018) Computing shortest paths in the plane with removable obstacles. In: SWAT 2018, pp 5:1\u20135:15"},{"issue":"1","key":"604_CR3","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF01840436","volume":"1","author":"T Asano","year":"1986","unstructured":"Asano T, Asano T, Guibas L, Hershberger J, Imai H (1986) Visibility of disjoint polygons. Algorithmica 1(1):49\u201363. https:\/\/doi.org\/10.1007\/BF01840436","journal-title":"Algorithmica"},{"key":"604_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational geometry: algorithms and applications","author":"Md Berg","year":"2008","unstructured":"Berg Md, Cheong O, Mv Kreveld, Overmars M (2008) Computational geometry: algorithms and applications, 3rd edn. Springer, Santa Clara","edition":"3"},{"issue":"3","key":"604_CR5","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B Chazelle","year":"1988","unstructured":"Chazelle B (1988) Functional approach to data structures and its use in multidimensional searching. SIAM J Comput 17(3):427\u2013462. https:\/\/doi.org\/10.1137\/0217026","journal-title":"SIAM J Comput"},{"key":"604_CR6","doi-asserted-by":"publisher","unstructured":"de\u00a0Rezende PJ, Lee DT, Wu YF (1985) Rectilinear shortest paths with rectangular barriers. In: SCG \u201985. ACM, New York, pp 204\u2013213. https:\/\/doi.org\/10.1145\/323233.323260","DOI":"10.1145\/323233.323260"},{"issue":"2","key":"604_CR7","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner H, Guibas LJ, Stolfi J (1986) Optimal point location in a monotone subdivision. SIAM J Comput 15(2):317\u2013340. https:\/\/doi.org\/10.1137\/0215023","journal-title":"SIAM J Comput"},{"key":"604_CR8","doi-asserted-by":"publisher","unstructured":"Erdmann M, Lozano-Perez T (1986) On multiple moving objects. In: Proceedings of the 1986 IEEE international conference on robotics and automation, vol 3, pp 1419\u20131424. https:\/\/doi.org\/10.1109\/ROBOT.1986.1087401","DOI":"10.1109\/ROBOT.1986.1087401"},{"key":"604_CR9","doi-asserted-by":"publisher","unstructured":"Fujimura K (1992) On motion planning amidst transient obstacles. In: Proceedings 1992 IEEE international conference on robotics and automation, vol 2, pp 1488\u20131493. https:\/\/doi.org\/10.1109\/ROBOT.1992.220041","DOI":"10.1109\/ROBOT.1992.220041"},{"key":"604_CR10","doi-asserted-by":"publisher","unstructured":"Fujimura K (1993) Motion planning using transient pixel representations. In: ICRA 1993, vol 2, pp 34\u201339. https:\/\/doi.org\/10.1109\/ROBOT.1993.292120","DOI":"10.1109\/ROBOT.1993.292120"},{"issue":"5","key":"604_CR11","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1177\/027836499401300502","volume":"13","author":"K Fujimura","year":"1994","unstructured":"Fujimura K (1994) Motion planning amid transient obstacles. Int J Robot Res 13(5):395\u2013407. https:\/\/doi.org\/10.1177\/027836499401300502","journal-title":"Int J Robot Res"},{"key":"604_CR12","doi-asserted-by":"publisher","unstructured":"Ghosh SK, Mount DM (1987) An output sensitive algorithm for computing visibility graphs. In: 28th annual symposium on foundations of computer science (SFCS 1987), pp 11\u201319. https:\/\/doi.org\/10.1109\/SFCS.1987.6","DOI":"10.1109\/SFCS.1987.6"},{"issue":"3","key":"604_CR13","doi-asserted-by":"publisher","first-page":"28:1","DOI":"10.1145\/1541885.1541889","volume":"5","author":"Y Giora","year":"2009","unstructured":"Giora Y, Kaplan H (2009) Optimal dynamic vertical ray shooting in rectilinear planar subdivisions. ACM Trans Algorithms 5(3):28:1\u201328:51. https:\/\/doi.org\/10.1145\/1541885.1541889","journal-title":"ACM Trans Algorithms"},{"issue":"6","key":"604_CR14","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. https:\/\/doi.org\/10.1137\/S0097539795289604","journal-title":"SIAM J Comput"},{"key":"604_CR15","unstructured":"Hershberger J, Kumar N, Suri S (2017) Shortest paths in the plane with obstacle violations. In: ESA 2017, pp 49:1\u201349:14"},{"issue":"1","key":"604_CR16","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D Kirkpatrick","year":"1983","unstructured":"Kirkpatrick D (1983) Optimal search in planar subdivisions. SIAM J Comput 12(1):28\u201335. https:\/\/doi.org\/10.1137\/0212002","journal-title":"SIAM J Comput"},{"key":"604_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877","volume-title":"Planning algorithms","author":"SM LaValle","year":"2006","unstructured":"LaValle SM (2006) Planning algorithms. Cambridge University Press, Cambridge"},{"issue":"3","key":"604_CR18","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0166-218X(96)80467-7","volume":"70","author":"D Lee","year":"1996","unstructured":"Lee D, Yang C, Wong C (1996) Rectilinear paths among rectilinear obstacles. Discrete Appl Math 70(3):185\u2013215. https:\/\/doi.org\/10.1016\/0166-218X(96)80467-7","journal-title":"Discrete Appl Math"},{"key":"604_CR19","doi-asserted-by":"publisher","unstructured":"Mitchell JSB (1993) Shortest paths among obstacles in the plane. In: Proceedings of the ninth annual symposium on computational geometry, SCG \u201993. ACM, New York, pp 308\u2013317. https:\/\/doi.org\/10.1145\/160985.161156","DOI":"10.1145\/160985.161156"},{"issue":"1\u20136","key":"604_CR20","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF01758836","volume":"8","author":"JS Mitchell","year":"1992","unstructured":"Mitchell JS (1992) $$l_1$$ shortest paths among polygonal obstacles in the plane. Algorithmica 8(1\u20136):55\u201388. https:\/\/doi.org\/10.1007\/BF01758836","journal-title":"Algorithmica"},{"issue":"2","key":"604_CR21","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/0196-6774(82)90016-5","volume":"3","author":"V Vaishnavi","year":"1982","unstructured":"Vaishnavi V, Wood D (1982) Rectilinear line segment intersection, layered segment trees, and dynamization. J Algorithms 3(2):160\u2013176. https:\/\/doi.org\/10.1016\/0196-6774(82)90016-5","journal-title":"J Algorithms"},{"key":"604_CR22","unstructured":"Wang H, Agarwal PK (1996) Approximation algorithms for curvature-constrained shortest paths. In: Proceedings of the seventh annual ACM-SIAM symposium on discrete algorithms, SODA \u201996. Society for Industrial and Applied Mathematics, Philadelphia, pp 409\u2013418. http:\/\/dl.acm.org\/citation.cfm?id=313852.314093"},{"issue":"4","key":"604_CR23","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0020-0190(85)90044-4","volume":"20","author":"E Welzl","year":"1985","unstructured":"Welzl E (1985) Constructing the visibility graph for n-line segments in $$o(n^2)$$ time. Inf Process Lett 20(4):167\u2013171. https:\/\/doi.org\/10.1016\/0020-0190(85)90044-4","journal-title":"Inf Process Lett"},{"issue":"4","key":"604_CR24","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1137\/0216049","volume":"16","author":"P Widmayer","year":"1987","unstructured":"Widmayer P, Wu Y, Wong C (1987) On some distance problems in fixed orientations. SIAM J Comput 16(4):728\u2013746. https:\/\/doi.org\/10.1137\/0216049","journal-title":"SIAM J Comput"},{"issue":"3","key":"604_CR25","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1137\/S0097539792229672","volume":"24","author":"C Yang","year":"1995","unstructured":"Yang C, Lee D, Wong C (1995) Rectilinear path problems among rectilinear obstacles revisited. SIAM J Comput 24(3):457\u2013472. https:\/\/doi.org\/10.1137\/S0097539792229672","journal-title":"SIAM J Comput"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00604-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00604-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00604-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,13]],"date-time":"2022-07-13T17:54:31Z","timestamp":1657734871000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00604-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,7]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["604"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00604-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,7]]},"assertion":[{"value":"7 July 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}