{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T05:40:07Z","timestamp":1746250807653,"version":"3.40.4"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2014,5,30]],"date-time":"2014-05-30T00:00:00Z","timestamp":1401408000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2015,10]]},"DOI":"10.1007\/s10472-014-9421-y","type":"journal-article","created":{"date-parts":[[2014,5,29]],"date-time":"2014-05-29T20:05:15Z","timestamp":1401393915000},"page":"27-51","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On finding a shortest isothetic path and its monotonicity inside a digital object"],"prefix":"10.1007","volume":"75","author":[{"given":"Mousumi","family":"Dutt","sequence":"first","affiliation":[]},{"given":"Arindam","family":"Biswas","sequence":"additional","affiliation":[]},{"given":"Partha","family":"Bhowmick","sequence":"additional","affiliation":[]},{"given":"Bhargab B.","family":"Bhattacharya","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,5,30]]},"reference":[{"issue":"9","key":"9421_CR1","doi-asserted-by":"crossref","first-page":"855","DOI":"10.1109\/34.57681","volume":"12","author":"AA Amini","year":"1990","unstructured":"Amini, A.A., Weymouth, T.E., Jain, R.C.: Using dynamic programming for solving variational problems in vision. IEEE Trans. Pattern Anal. Mach. Intell. 12(9), 855\u2013867 (1990)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"9421_CR2","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/S0020-0190(02)00502-1","volume":"86","author":"E Arkin","year":"2003","unstructured":"Arkin, E., Mitchell, J., Piatko, C.: Minimum-link watchman tours. Inf. Process. Lett. 86, 203\u2013207 (2003)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9421_CR3","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0925-7721(91)90010-C","volume":"1","author":"M de Berg","year":"1991","unstructured":"de Berg, M.: On rectilinear link distance. Comput. Geom. Theory Appl. 1(1), 13\u201334 (1991)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9421_CR4","doi-asserted-by":"crossref","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.: Computational Geometry Algorithms And Applications. Springer-Verlag, Heidelberg (2008)"},{"key":"9421_CR5","volume-title":"Finding shortest paths in the presence of orthogonal obstacles using a combined l1 and link metric. In: Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory, LNCS, vol. 447, pp. 213\u2013224","author":"M de Berg","year":"1990","unstructured":"de Berg, M., van Kreveld, M., Nilsson, B.J., Overmars, M.H.: Finding shortest paths in the presence of orthogonal obstacles using a combined l 1 and link metric. In: Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory, LNCS, vol. 447, pp. 213\u2013224. Springer-Verlag, Bergen (1990)"},{"key":"9421_CR6","doi-asserted-by":"crossref","DOI":"10.1145\/1185448.1185626","volume-title":"Distance- and curvature-constrained shortest paths and an application in mission planning. In: Proceedings of the 44th Annual Southeast Regional Conference, ACM-SE 44, pp. 766\u2013767","author":"A Berger","year":"2006","unstructured":"Berger, A., Razouk, N., Angelides, G.: Distance- and curvature-constrained shortest paths and an application in mission planning. In: Proceedings of the 44th Annual Southeast Regional Conference, ACM-SE 44, pp. 766\u2013767. ACM, New York (2006)"},{"key":"9421_CR7","volume-title":"TIPS: On Finding a Tight Isothetic Polygonal Shape Covering a 2D Object. In: Proceedings of the 14th Scandinavian Conference on Image Analysis, LNCS, vol. 3540, pp. 930\u2013939","author":"A Biswas","year":"2005","unstructured":"Biswas, A., Bhowmick, P., Bhattacharya, B.B.: TIPS: On Finding a Tight Isothetic Polygonal Shape Covering a 2D Object. In: Proceedings of the 14th Scandinavian Conference on Image Analysis, LNCS, vol. 3540, pp. 930\u2013939. Springer-Verlag, Joensuu (2005)"},{"issue":"4","key":"9421_CR8","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/j.jvcir.2010.02.001","volume":"21","author":"A Biswas","year":"2010","unstructured":"Biswas, A., Bhowmick, P., Bhattacharya, B.B.: Construction of isothetic covers of a digital object: A combinatorial approach. J. Vis. Commun. Image Represent. 21(4), 295\u2013310 (2010)","journal-title":"J. Vis. Commun. Image Represent."},{"issue":"7","key":"9421_CR9","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1016\/S0167-8655(97)00076-7","volume":"18","author":"M Buckley","year":"1997","unstructured":"Buckley, M., Yang, J.: Regularised shortest-path extraction. Pattern Recog. Lett. 18(7), 621\u2013629 (1997)","journal-title":"Pattern Recog. Lett."},{"key":"9421_CR10","doi-asserted-by":"crossref","unstructured":"B\u00fclow, T., Klette, R.: Approximation of 3d shortest polygons in simple cube curves. In: Digital and Image Geometry, Lecture Notes in Computer Science, pp. 285\u2013298. Springer (2001)","DOI":"10.1007\/3-540-45576-0_17"},{"issue":"3","key":"9421_CR11","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/0020-0255(92)90072-G","volume":"63","author":"WP Chin","year":"1992","unstructured":"Chin, W.P., Ntafos, S.: The zookeeper route problem. Inf. Sci. 63(3), 245\u2013259 (1992)","journal-title":"Inf. Sci."},{"key":"9421_CR12","volume-title":"Rectilinear shortest paths through polygonal obstacles in $O(n (\\log n)^{2})$O(n(logn)2) time. In: Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG \u201987, pp. 251\u2013257","author":"KL Clarkson","year":"1987","unstructured":"Clarkson, K.L., Kapoor, S., Vaidya, P.: Rectilinear shortest paths through polygonal obstacles in O ( n ( log n ) 2 ) $O(n (\\log n)^{2})$ time. In: Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG \u201987, pp. 251\u2013257. ACM, New York (1987)"},{"issue":"2","key":"9421_CR13","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1109\/TPAMI.2004.1262194","volume":"26","author":"D Coeurjolly","year":"2004","unstructured":"Coeurjolly, D., Klette, R.: A comparative evaluation of length estimators of digital curves. IEEE Trans. Pattern Anal. Mach. Intell. 26(2), 252\u2013258 (2004)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"2","key":"9421_CR14","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/0022-0000(89)90043-3","volume":"39","author":"JC Culberson","year":"1989","unstructured":"Culberson, J.C., Reckhow, R.A.: Orthogonally convex coverings of orthogonal polygons without holes. J. Comput. Syst. Sci. 39(2), 166\u2013204 (1989)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9421_CR15","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0196-6774(03)00047-6","volume":"48","author":"A Dumitrescu","year":"2003","unstructured":"Dumitrescu, A., Mitchell, J.S.B.: Approximation algorithms for TSP with neighborhoods in the plane. J. Algorithms 48(1), 135\u2013159 (2003)","journal-title":"J. Algorithms"},{"key":"9421_CR16","volume-title":"On finding shortest isothetic path inside a digital object. In: Barneva, R.P. (ed.) Proceedings of the 15th International Workshop on Combinatorial Image Analysis: IWCIA\u201912, LNCS, vol. 7655, pp. 1\u201315","author":"M Dutt","year":"2012","unstructured":"Dutt, M., Biswas, A., Bhowmick, P., Bhattacharya, B.B.: On finding shortest isothetic path inside a digital object. In: Barneva, R.P. (ed.) Proceedings of the 15th International Workshop on Combinatorial Image Analysis: IWCIA\u201912, LNCS, vol. 7655, pp. 1\u201315. Springer-Verlag, Austin (2012)"},{"key":"9421_CR17","volume-title":"Handbook of Computer Aided Geometric Design","author":"G Farin","year":"2002","unstructured":"Farin, G., Hoschek, J., Kim, M.S.: Handbook of Computer Aided Geometric Design. Elsevier Science B. V., North Holland (2002)"},{"issue":"4","key":"9421_CR18","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M Garey","year":"1977","unstructured":"Garey, M., Johnson, D.: The rectilinear steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"9421_CR19","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511543340","volume-title":"Visibility Algorithms in the Plane","author":"SK Ghosh","year":"2007","unstructured":"Ghosh, S.K.: Visibility Algorithms in the Plane. Cambridge University Press, New York (2007)"},{"key":"9421_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-48686-0_47","volume-title":"A fast approximation algorithm for TSP with neighborhoods and red-blues separation. In: Proceedings of the 5th Annual International Conference on Computing and Combinatorics, COCOON \u201999, pp. 473\u2013482","author":"J Gudmundsson","year":"1999","unstructured":"Gudmundsson, J., Levcopoulos, C.: A fast approximation algorithm for TSP with neighborhoods and red-blues separation. In: Proceedings of the 5th Annual International Conference on Computing and Combinatorics, COCOON \u201999, pp. 473\u2013482. Springer-Verlag, Berlin, Heidelberg (1999)"},{"issue":"5","key":"9421_CR21","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1109\/TCAD.2010.2098930","volume":"30","author":"T Huang","year":"2011","unstructured":"Huang, T., Li, L., Young, E.F.Y.: On the construction of optimal obstacle-avoiding rectilinear steiner minimum trees. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 30(5), 718\u2013731 (2011)","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst."},{"key":"9421_CR22","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1016\/j.comgeo.2009.02.005","volume":"42","author":"R Inkulu","year":"2009","unstructured":"Inkulu, R., Kapoor, S.: Planar rectilinear shortest path computation using corridors. Comput. Geom. Theory Appl. 42, 873\u2013884 (2009)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"4","key":"9421_CR23","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1023\/A:1009758919736","volume":"1","author":"M Karpinski","year":"1997","unstructured":"Karpinski, M., Zelikovsky, A.: New approximation algorithms for the steiner tree problem. J. Comb. Optim. 1(4), 47\u201365 (1997)","journal-title":"J. Comb. Optim."},{"key":"9421_CR24","volume-title":"Digital Geometry: Geometric Methods for Picture Analysis","author":"R Klette","year":"2004","unstructured":"Klette, R., Rosenfeld, A.: Digital Geometry: Geometric Methods for Picture Analysis. Morgan Kaufmann, San Francisco (2004)"},{"key":"9421_CR25","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1002\/net.3230110307","volume":"11","author":"RC Larson","year":"1981","unstructured":"Larson, R.C., Li, V.O.: Finding minimum rectilinear distance paths in the presence of barriers. Networks 11, 285\u2013304 (1981)","journal-title":"Networks"},{"key":"9421_CR26","volume-title":"Finding the shortest path between two points in a simple polygon by applying a rubberband algorithm. In: Proceedings of the First Pacific Rim conference on Advances in Image and Video Technology, PSIVT\u201906, vol. 4319, pp. 280\u2013291","author":"F Li","year":"2006","unstructured":"Li, F., Klette, R.: Finding the shortest path between two points in a simple polygon by applying a rubberband algorithm. In: Proceedings of the First Pacific Rim conference on Advances in Image and Video Technology, PSIVT\u201906, vol. 4319, pp. 280\u2013291. Springer-Verlag, Berlin, Heidelberg (2006)"},{"key":"9421_CR27","unstructured":"Lin, G.H., Xue, G.: A linear-time heuristic for rectilinear steiner trees. In: Proceedings., First Great Lakes Symposium on VLSI, pp. 152\u2013156. IEEE (1991)"},{"key":"9421_CR28","doi-asserted-by":"crossref","unstructured":"Lin, G.H., Xue, G.: Balancing steiner minimum trees and shortest-path trees in the rectilinear plane. In: Proceedings of the 1999 IEEE International Symposium on Circuits and Systems, ISCAS\u201999, vol. 6, pp. 117\u2013120. IEEE (1999)","DOI":"10.1109\/ISCAS.1999.780109"},{"key":"9421_CR29","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1109\/TPAMI.2007.41","volume":"29","author":"H Ling","year":"2007","unstructured":"Ling, H., Jacobs, D.W.: Shape classification using the inner-distance. IEEE Trans. Pattern Anal. Mach. Intell. 29, 286\u2013299 (2007)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"10","key":"9421_CR30","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1145\/359156.359164","volume":"22","author":"T Lozano-Perez","year":"1979","unstructured":"Lozano-Perez, T., Wesley, M.A.: An algorithm for planning collision-free paths among polyhedral obstacles. Mag. Commun. ACM 22(10), 560\u2013570 (1979)","journal-title":"Mag. Commun. ACM"},{"key":"9421_CR31","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0925-7721(92)90014-J","volume":"1","author":"S Ntafos","year":"1992","unstructured":"Ntafos, S.: Watchman routes under limited visibility. Comput. Geom. Theory Appl. 1, 149\u2013170 (1992)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9421_CR32","volume-title":"Rectilinear shortest paths with rectangular barriers. In: Proceedings of the 1st Annual Symposium on Computational Geometry, SCG \u201985, pp. 204\u2013213","author":"PJ de Resende","year":"1985","unstructured":"de Resende, P.J., Lee, D.T., Wu, Y.F.: Rectilinear shortest paths with rectangular barriers. In: Proceedings of the 1st Annual Symposium on Computational Geometry, SCG \u201985, pp. 204\u2013213. ACM, New York (1985)"},{"key":"9421_CR33","volume-title":"On shortest paths in polyhedral spaces. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC \u201984, vol. 15, pp. 193\u2013215","author":"M Sharir","year":"1986","unstructured":"Sharir, M., Schorr, A.: On shortest paths in polyhedral spaces. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC \u201984, vol. 15, pp. 193\u2013215. ACM, New York (1986)"},{"key":"9421_CR34","unstructured":"Sheng, Y.B., Ke, W.Y., Ping, L.J.: Finding the shortest path between two points in a simple polygon by applying a rubberband algorithm. In: WRI World Congress on Software Engineering, 2009, WCSE \u201909, vol. 1, pp. 239\u2013243 (2009)"},{"key":"9421_CR35","first-page":"59","volume-title":"Theoretical Foundations of Computer Vision, vol. 69","author":"F Sloboda","year":"1992","unstructured":"Sloboda, F., Zatko, B., Ferianc, P.: Minimum perimeter polygon and its application. In: Klette, R., Kropatsch, W. (eds.) Theoretical Foundations of Computer Vision, vol. 69, pp 59\u201370. Mathematical Research, Akademie Verlag, Berlin (1992)"},{"key":"9421_CR36","first-page":"113","volume-title":"Advances in Digital and Computational Geometry","author":"F Sloboda","year":"1998","unstructured":"Sloboda, F., Zatko, B., Stoer, J.: On approximation of planar one-dimensional continua. In: Klette, R., Rosenfeld, A., Sloboda, F. (eds.) Advances in Digital and Computational Geometry, pp 113\u2013160. Springer, Singapore (1998)"},{"issue":"3","key":"9421_CR37","doi-asserted-by":"crossref","first-page":"709","DOI":"10.1016\/S0031-3203(02)00085-7","volume":"36","author":"C Sun","year":"2003","unstructured":"Sun, C., Pallottino, S.: Circular shortest path in images. Pattern Recog. 36(3), 709\u2013719 (2003)","journal-title":"Pattern Recog."},{"issue":"2\u20133","key":"9421_CR38","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/S0166-218X(03)00451-7","volume":"136","author":"X Tan","year":"2004","unstructured":"Tan, X.: Approximation algorithms for the watchman route and zookeeper\u2019s problems. Discret. Appl. Math. 136(2\u20133), 363\u2013376 (2004)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"9421_CR39","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0020-0190(03)00284-9","volume":"87","author":"X Tan","year":"2003","unstructured":"Tan, X., Hirata, T.: Finding shortest safari routes in simple polygons. Inf. Process. Lett. 87(4), 179\u2013186 (2003)","journal-title":"Inf. Process. Lett."},{"key":"9421_CR40","unstructured":"Wei, X.: Monotone path queries and monotone subdivision problems in polygonal domains, Ph.D. thesis, Hong Kong University of Science and Technology (2010)"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-014-9421-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-014-9421-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-014-9421-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T04:59:17Z","timestamp":1746248357000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-014-9421-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,30]]},"references-count":40,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["9421"],"URL":"https:\/\/doi.org\/10.1007\/s10472-014-9421-y","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"type":"print","value":"1012-2443"},{"type":"electronic","value":"1573-7470"}],"subject":[],"published":{"date-parts":[[2014,5,30]]}}}