{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T19:26:19Z","timestamp":1725823579198},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_77","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T06:07:39Z","timestamp":1434694059000},"page":"947-959","source":"Crossref","is-referenced-by-count":1,"title":["An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains"],"prefix":"10.1007","author":[{"given":"Joseph S. B.","family":"Mitchell","sequence":"first","affiliation":[]},{"given":"Valentin","family":"Polishchuk","sequence":"additional","affiliation":[]},{"given":"Mikko","family":"Sysikaski","sequence":"additional","affiliation":[]},{"given":"Haitao","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"issue":"4","key":"77_CR1","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.: Triangulating disjoint Jordan chains. International Journal of Computational Geometry and Applications 4(4), 475\u2013481 (1994)","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"77_CR2","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/0925-7721(91)90010-C","volume":"1","author":"M Berg de","year":"1991","unstructured":"de Berg, M.: On rectilinear link distance. Computational Geometry: Theory and Applications 1, 13\u201334 (1991)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"77_CR3","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BF02574703","volume":"6","author":"B Chazelle","year":"1991","unstructured":"Chazelle, B.: Triangulating a simple polygon in linear time. Discrete and Computational Geometry 6, 485\u2013524 (1991)","journal-title":"Discrete and Computational Geometry"},{"key":"77_CR4","doi-asserted-by":"crossref","unstructured":"Chen, D., Inkulu, R., Wang, H.: Two-point \n                    \n                      \n                    \n                    $$L_1$$\n                    \n                      \n                        \n                          L\n                          1\n                        \n                      \n                    \n                   shortest path queries in the plane. In: Proc. of the 30th Annual Symposium on Computational Geometry (SoCG), pp. 406\u2013415 (2014)","DOI":"10.1145\/2582112.2582125"},{"key":"77_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/978-3-642-23719-5_41","volume-title":"Algorithms \u2013 ESA 2011","author":"Danny Z Chen","year":"2011","unstructured":"Chen, Danny Z., Wang, Haitao: A Nearly Optimal Algorithm for Finding L\n                  \n                    \n                      \n                    \n                    $$_\\text{1 }$$\n                    \n                      \n                        \n                          \n                            \n                            1\n                          \n                          \n                        \n                      \n                    \n                   Shortest Paths among Polygonal Obstacles in the Plane. In: Demetrescu, Camil, Halld\u00f3rsson, Magn\u00fas M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 481\u2013492. Springer, Heidelberg (2011)"},{"key":"77_CR6","doi-asserted-by":"crossref","unstructured":"Das, G., Narasimhan, G.: Geometric searching and link distance. In: Proc. of the 2nd Workshop of Algorithms and Data Structures (WADS), pp. 261\u2013272 (1991)","DOI":"10.1007\/BFb0028268"},{"issue":"2","key":"77_CR7","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Guibas, L., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM Journal on Computing 15(2), 317\u2013340 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"77_CR8","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0196-6774(91)90024-S","volume":"12","author":"S Ghosh","year":"1991","unstructured":"Ghosh, S.: Computing the visibility polygon from a convex set and related problems. Journal of Algorithms 12, 75\u201395 (1991)","journal-title":"Journal of Algorithms"},{"key":"77_CR9","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.: Computing minimum length paths of a given homotopy class. Computational Geometry: Theory and Applications 4, 63\u201397 (1994)","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"2","key":"77_CR10","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1137\/0215033","volume":"15","author":"H Imai","year":"1986","unstructured":"Imai, H., Asano, T.: Efficient algorithms for geometric graph search problems. SIAM Journal on Computing 15(2), 478\u2013494 (1986)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"77_CR11","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/PL00009323","volume":"18","author":"S Kapoor","year":"1997","unstructured":"Kapoor, S., Maheshwari, S., Mitchell, J.: An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane. Discrete and Computational Geometry 18(4), 377\u2013383 (1997)","journal-title":"Discrete and Computational Geometry"},{"key":"77_CR12","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF01206332","volume":"14","author":"A Lingas","year":"1995","unstructured":"Lingas, A., Maheshwari, A., Sack, J.R.: Parallel algorithms for rectilinear link distance problems. Algorithmica 14, 261\u2013289 (1995)","journal-title":"Algorithmica"},{"key":"77_CR13","doi-asserted-by":"crossref","unstructured":"Maheshwari, A., Sack, J.R., Djidjev, H.: Link distance problems. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 519\u2013558. Elsevier, Amsterdam (2000)","DOI":"10.1016\/B978-044482537-7\/50013-9"},{"key":"77_CR14","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/j.comgeo.2013.12.005","volume":"47","author":"J Mitchell","year":"2014","unstructured":"Mitchell, J., Polishchuk, V., Sysikaski, M.: Minimum-link paths revisited. Computational Geometry: Theory and Applications 47, 651\u2013667 (2014)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"77_CR15","unstructured":"Mitchell, J., Polishchuk, V., Sysikaski, M., Wang, H.: An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains (2015). \n                    arXiv:1504.06842"},{"key":"77_CR16","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/BF01758855","volume":"8","author":"J Mitchell","year":"1992","unstructured":"Mitchell, J., Rote, G., Woeginger, G.: Minimum-link paths among obstacles in the plane. Algorithmica 8, 431\u2013459 (1992)","journal-title":"Algorithmica"},{"key":"77_CR17","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0925-7721(95)00006-U","volume":"5","author":"J Mitchell","year":"1995","unstructured":"Mitchell, J., Suri, S.: Separation and approximation of polyhedral objects. Computational Geometry: Theory and Applications 5, 95\u2013114 (1995)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"77_CR18","unstructured":"Sato, M., Sakanaka, J., Ohtsuki, T.: A fast line-search method based on a tile plane. In: Proc. of the IEEE International Symposium on Circuits and Systems, pp. 588\u2013597 (1987)"},{"key":"77_CR19","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1142\/S0218195996000149","volume":"6","author":"S Schuierer","year":"1996","unstructured":"Schuierer, S.: An optimal data structure for shortest rectilinear path queries in a simple rectilinear polygon. International Journal of Compututational Geometry and Applications 6, 205\u2013226 (1996)","journal-title":"International Journal of Compututational Geometry and Applications"},{"issue":"1","key":"77_CR20","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0734-189X(86)90127-1","volume":"35","author":"S Suri","year":"1986","unstructured":"Suri, S.: A linear time algorithm with minimum link paths inside a simple polygon. Computer Vision, Graphics, and Image Processing 35(1), 99\u2013110 (1986)","journal-title":"Computer Vision, Graphics, and Image Processing"},{"key":"77_CR21","unstructured":"Suri, S.: Minimum link paths in polygons and related problems. Ph.D. thesis, Johns Hopkins University, Baltimore, MD (1987)"},{"key":"77_CR22","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1109\/70.88124","volume":"6","author":"S Suri","year":"1990","unstructured":"Suri, S.: On some link distance problems in a simple polygon. IEEE Transactions on Robotics and Automation 6, 108\u2013113 (1990)","journal-title":"IEEE Transactions on Robotics and Automation"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_77","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T03:23:34Z","timestamp":1559186614000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_77"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_77","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}