{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,31]],"date-time":"2025-07-31T00:39:36Z","timestamp":1753922376857,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,1,20]],"date-time":"2020-01-20T00:00:00Z","timestamp":1579478400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,20]],"date-time":"2020-01-20T00:00:00Z","timestamp":1579478400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1525817"],"award-info":[{"award-number":["CCF-1525817"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s00453-020-00673-y","type":"journal-article","created":{"date-parts":[[2020,1,20]],"date-time":"2020-01-20T11:03:09Z","timestamp":1579518189000},"page":"1813-1832","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Shortest Paths in the Plane with Obstacle Violations"],"prefix":"10.1007","volume":"82","author":[{"given":"John","family":"Hershberger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9356-526X","authenticated-orcid":false,"given":"Neeraj","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Subhash","family":"Suri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,20]]},"reference":[{"issue":"3","key":"673_CR1","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/j.comgeo.2007.09.001","volume":"40","author":"M Abellanas","year":"2008","unstructured":"Abellanas, M., Garc\u00eda, A., Hurtado, F., Tejel, J., Urrutia, J.: Augmenting the connectivity of geometric graphs. Comput. Geom. 40(3), 220\u2013230 (2008)","journal-title":"Comput. Geom."},{"key":"673_CR2","unstructured":"Agarwal, P.K., Kumar, N., Sintos, S., Suri, S.: Computing shortest paths in the plane with removable obstacles. In: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), vol. 101, pp. 5:1\u20135:15 (2018)"},{"key":"673_CR3","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Upper Saddle River (1993)"},{"issue":"9","key":"673_CR4","first-page":"557","volume":"68","author":"T Asano","year":"1985","unstructured":"Asano, T.: An efficient algorithm for finding the visibility polygon for a polygonal region with holes. IEICE Trans. (1976\u20131990) 68(9), 557\u2013559 (1985)","journal-title":"IEICE Trans. (1976\u20131990)"},{"issue":"1\u20134","key":"673_CR5","doi-asserted-by":"crossref","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.: Visibility of disjoint polygons. Algorithmica 1(1\u20134), 49\u201363 (1986)","journal-title":"Algorithmica"},{"key":"673_CR6","unstructured":"Bandyapadhyaya, S., Kumar, N., Suri, S., Varadrajan, K.: Improved approximation bounds for the minimum constraint removal problem. In: 21st International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) (2018)"},{"key":"673_CR7","unstructured":"Carufel, J.L.D., Grimm, C., Maheshwari, A., Smid, M.: Minimizing the continuous diameter when augmenting paths and cycles with shortcuts. In: 15th Scandinavian Symposium and Workshops on Algorithm Theory, pp. 27:1\u201327:14 (2016)"},{"issue":"4","key":"673_CR8","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1137\/S0097539703439404","volume":"34","author":"TM Chan","year":"2005","unstructured":"Chan, T.M.: Low-dimensional linear programming with violations. SIAM J. Comput. 34(4), 879\u2013893 (2005)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"673_CR9","first-page":"26:1","volume":"11","author":"DZ Chen","year":"2015","unstructured":"Chen, D.Z., Wang, H.: Computing shortest paths among curved obstacles in the plane. ACM Trans. Algorithms 11(4), 26:1\u201326:46 (2015)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"673_CR10","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Guibas, L.J., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM J. Comput. 15(2), 317\u2013340 (1986)","journal-title":"SIAM J. Comput."},{"key":"673_CR11","doi-asserted-by":"crossref","unstructured":"Eiben, E., Gemmell, J., Kanj, I., Youngdahl, A.: Improved results for minimum constraint removal. In: Proceedings of AAAI, AAAI press (2018)","DOI":"10.1609\/aaai.v32i1.12100"},{"key":"673_CR12","doi-asserted-by":"crossref","unstructured":"Eriksson-Bique, S., Hershberger, J., Polishchuk, V., Speckmann, B., Suri, S., Talvitie, T., Verbeek, K., Y\u0131ld\u0131z, H.: Geometric $$k$$ shortest paths. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1616\u20131625 (2015)","DOI":"10.1137\/1.9781611973730.107"},{"issue":"1","key":"673_CR13","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1137\/050635675","volume":"38","author":"M Farshi","year":"2008","unstructured":"Farshi, M., Giannopoulos, P., Gudmundsson, J.: Improving the stretch factor of a geometric network by edge augmentation. SIAM J. Comput. 38(1), 226\u2013240 (2008)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"673_CR14","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1137\/0220055","volume":"20","author":"SK Ghosh","year":"1991","unstructured":"Ghosh, S.K., Mount, D.M.: An output-sensitive algorithm for computing visibility graphs. SIAM J. Comput. 20(5), 888\u2013910 (1991)","journal-title":"SIAM J. Comput."},{"issue":"1\u20134","key":"673_CR15","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"L Guibas","year":"1987","unstructured":"Guibas, L., Hershberger, J., Leven, D., Sharir, M., Tarjan, R.E.: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica 2(1\u20134), 209\u2013233 (1987)","journal-title":"Algorithmica"},{"key":"673_CR16","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Koltun, V.: Separability with outliers. 16th International Symposium on Algorithms and Computation, pp. 28\u201339 (2005)","DOI":"10.1007\/11602613_5"},{"key":"673_CR17","unstructured":"Hershberger, J., Kumar, N., Suri, S.: Shortest paths in the plane with obstacle violations. In: 25th Annual European Symposium on Algorithms (ESA 2017), vol.\u00a087, pp. 49:1\u201349:14 (2017)"},{"issue":"2","key":"673_CR18","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0925-7721(94)90010-8","volume":"4","author":"J Hershberger","year":"1994","unstructured":"Hershberger, J., Snoeyink, J.: Computing minimum length paths of a given homotopy class. Comput. Geom. 4(2), 63\u201397 (1994)","journal-title":"Comput. Geom."},{"issue":"6","key":"673_CR19","doi-asserted-by":"crossref","first-page":"2215","DOI":"10.1137\/S0097539795289604","volume":"28","author":"J Hershberger","year":"1999","unstructured":"Hershberger, J., Suri, S.: An optimal algorithm for Euclidean shortest paths in the plane. SIAM J. Comput. 28(6), 2215\u20132256 (1999)","journal-title":"SIAM J. Comput."},{"key":"673_CR20","doi-asserted-by":"crossref","unstructured":"Hershberger, J., Suri, S., Y\u0131ld\u0131z, H.: A near-optimal algorithm for shortest paths among curved obstacles in the plane. In: Proceedings of the Twenty-Ninth Annual Symposium on Computational Geometry, pp. 359\u2013368 (2013)","DOI":"10.1145\/2462356.2462374"},{"key":"673_CR21","doi-asserted-by":"crossref","unstructured":"Kapoor, S., Maheshwari, S.N.: Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles. In: Proceedings of the Fourth Annual Symposium on Computational Geometry, pp. 172\u2013182 (1988)","DOI":"10.1145\/73393.73411"},{"issue":"1","key":"673_CR22","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.: Optimal search in planar subdivisions. SIAM J. Comput. 12(1), 28\u201335 (1983)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"673_CR23","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/net.3230140304","volume":"14","author":"DT Lee","year":"1984","unstructured":"Lee, D.T., Preparata, F.P.: Euclidean shortest paths in the presence of rectilinear barriers. Networks 14(3), 393\u2013410 (1984)","journal-title":"Networks"},{"key":"673_CR24","first-page":"1","volume":"80","author":"A Maheshwari","year":"2016","unstructured":"Maheshwari, A., Nandy, S.C., Pattanayak, D., Roy, S., Smid, M.: Geometric path problems with violations. Algorithmica 80, 1\u201324 (2016)","journal-title":"Algorithmica"},{"issue":"4","key":"673_CR25","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02570713","volume":"14","author":"J Matou\u0161ek","year":"1995","unstructured":"Matou\u0161ek, J.: On geometric optimization with few violated constraints. Discret. Comput. Geom. 14(4), 365\u2013384 (1995)","journal-title":"Discret. Comput. Geom."},{"issue":"1","key":"673_CR26","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF01530888","volume":"3","author":"JSB Mitchell","year":"1991","unstructured":"Mitchell, J.S.B.: A new algorithm for shortest paths among obstacles in the plane. Ann. Math. Artif. Intell. 3(1), 83\u2013105 (1991)","journal-title":"Ann. Math. Artif. Intell."},{"issue":"3","key":"673_CR27","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1142\/S0218195996000216","volume":"6","author":"JSB Mitchell","year":"1996","unstructured":"Mitchell, J.S.B.: Shortest paths among obstacles in the plane. Int. J. Comput. Geom. Appl. 6(3), 309\u2013332 (1996)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"1","key":"673_CR28","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/102782.102784","volume":"38","author":"JSB Mitchell","year":"1991","unstructured":"Mitchell, J.S.B., Papadimitriou, C.H.: The weighted region problem: finding shortest paths through a weighted planar subdivision. J. ACM (JACM) 38(1), 18\u201373 (1991)","journal-title":"J. ACM (JACM)"},{"key":"673_CR29","doi-asserted-by":"crossref","unstructured":"Overmars, M.H., Welzl, E.: New methods for computing visibility graphs. In: Proceedings of the Fourth Annual Symposium on Computational Geometry, pp. 164\u2013171 (1988)","DOI":"10.1145\/73393.73410"},{"issue":"2","key":"673_CR30","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0020-0190(86)90045-1","volume":"23","author":"H Rohnert","year":"1986","unstructured":"Rohnert, H.: Shortest paths in the plane with convex polygonal obstacles. Inf. Process. Lett. 23(2), 71\u201376 (1986)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"673_CR31","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0020-0190(94)00134-0","volume":"52","author":"T Roos","year":"1994","unstructured":"Roos, T., Widmayer, P.: $$k$$-violation linear programming. Inf. Process. Lett. 52(2), 109\u2013114 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"673_CR32","doi-asserted-by":"crossref","first-page":"982","DOI":"10.1145\/185675.185795","volume":"41","author":"JA Storer","year":"1994","unstructured":"Storer, J.A., Reif, J.H.: Shortest paths in the plane with polygonal obstacles. J. ACM (JACM) 41(5), 982\u20131012 (1994)","journal-title":"J. ACM (JACM)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00673-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00673-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00673-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,12]],"date-time":"2022-10-12T00:21:01Z","timestamp":1665534061000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00673-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,20]]},"references-count":32,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["673"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00673-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,1,20]]},"assertion":[{"value":"26 July 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}