{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:55:51Z","timestamp":1787385351382,"version":"build-2736575974"},"publisher-location":"Berlin\/Heidelberg","reference-count":34,"publisher":"Springer-Verlag","isbn-type":[{"value":"3540543430","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0028273","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T05:52:14Z","timestamp":1132638734000},"page":"331-342","source":"Crossref","is-referenced-by-count":20,"title":["Computing minimum length paths of a given homotopy class"],"prefix":"10.1007","author":[{"given":"John","family":"Hershberger","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jack","family":"Snoeyink","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"1","key":"30_CR1","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/0890-5401(89)90049-7","volume":"83","author":"A. Aggarwal","year":"1989","unstructured":"A. Aggarwal, H. Booth, J. O'Rourke, S. Suri, and C. K. Yap. Finding minimal convex nested polygons. Information and Computation, 83(1):98\u2013110, Oct. 1989.","journal-title":"Information and Computation"},{"key":"30_CR2","volume-title":"Basic Topology","author":"M. A. Armstrong","year":"1979","unstructured":"M. A. Armstrong. Basic Topology. McGraw-Hill, London, 1979."},{"key":"30_CR3","unstructured":"B. Baumgart. A polyhedral representation for computer vision. In Proceedings of the AFIPS National Computer Conference, pages 589\u2013596, 1975."},{"key":"30_CR4","unstructured":"B. Bhattacharya and G. T. Toussaint. A linear algorithm for determining translation separability of two simple polygons. Technical Report SOCS-86.1, School of Computer Science, McGill University, Montreal, 1986."},{"key":"30_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-62035-5","volume-title":"An Introduction to the Geometry of Numbers","author":"J. W. S. Cassels","year":"1959","unstructured":"J. W. S. Cassels. An Introduction to the Geometry of Numbers. Springer-Verlag, Berlin, 1959."},{"key":"30_CR6","doi-asserted-by":"crossref","unstructured":"B. Chazelle. A theorem on polygon cutting with applications. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, pages 339\u2013349, 1982.","DOI":"10.1109\/SFCS.1982.58"},{"key":"30_CR7","doi-asserted-by":"crossref","unstructured":"B. Chazelle. Triangulating a simple polygon in linear time. In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, pages 220\u2013230, 1990.","DOI":"10.1109\/FSCS.1990.89541"},{"key":"30_CR8","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson, S. Kapoor, and P. M. Vaidya. Rectilinear shortest paths through polygonal obstacles in O(n log2 n) time. In Proceedings of the Third Annual ACM Symposium on Computational Geometry, pages 251\u2013257, 1987.","DOI":"10.1145\/41958.41985"},{"key":"30_CR9","unstructured":"J. Czyzowicz, P. Egyed, H. Everett, D. Rappaport, T. Shermer, D. Souvaine, G. Toussaint, and J. Urrutia. The aquarium keeper's problem. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 459\u2013464, Jan. 1991."},{"key":"30_CR10","unstructured":"M. de Berg. On rectilinear link distance. Technical Report RUU-CS-89-13, Vakgroep Informatica, Rijksuniversiteit Utrecht, May 1989."},{"key":"30_CR11","doi-asserted-by":"crossref","unstructured":"M. de Berg. Translating polygons with applications to hidden surface removal. In SWAT 90: Second Scandinavian Workshop on Algorithm Theory, number 447 in Lecture Notes in Computer Science, pages 60\u201370. Springer-Verlag, 1990.","DOI":"10.1007\/3-540-52846-6_78"},{"key":"30_CR12","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF02187714","volume":"4","author":"P. J. Rezende de","year":"1989","unstructured":"P. J. de Rezende, D. T. Lee, and Y. F. Wu. Rectilinear shortest paths with rectangular barriers. Discrete and Computational Geometry, 4:41\u201353, 1989.","journal-title":"Discrete and Computational Geometry"},{"key":"30_CR13","doi-asserted-by":"crossref","unstructured":"S. Gao, M. Jerrum, M. Kaufmann, K. Mehlhorn, W. R\u00fclling, and C. Storb. On continuous homotopic one layer routing. In Proceedings of the Third Annual ACM Symposium on Computational Geometry, pages 392\u2013402, 1987.","DOI":"10.1145\/73393.73433"},{"key":"30_CR14","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0196-6774(91)90024-S","volume":"12","author":"S. K. Ghosh","year":"1991","unstructured":"S. K. Ghosh. Computing the visibility polygon from a convex set and related problems. Journal of Algorithms, 12:75\u201395, 1991.","journal-title":"Journal of Algorithms"},{"key":"30_CR15","doi-asserted-by":"crossref","unstructured":"S. K. Ghosh and D. M. Mount. An output sensitive algorithm for computing visibility graphs. In Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, pages 11\u201319, 1987.","DOI":"10.1109\/SFCS.1987.6"},{"key":"30_CR16","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R. Graham","year":"1972","unstructured":"R. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1:132\u2013133, 1972.","journal-title":"Information Processing Letters"},{"key":"30_CR17","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"L. Guibas","year":"1987","unstructured":"L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. Tarjan. Linear time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2:209\u2013233, 1987.","journal-title":"Algorithmica"},{"issue":"2","key":"30_CR18","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/282918.282923","volume":"4","author":"L. Guibas","year":"1985","unstructured":"L. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Transactions on Graphics, 4(2):74\u2013123, 1985.","journal-title":"ACM Transactions on Graphics"},{"issue":"2","key":"30_CR19","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/0022-0000(89)90041-X","volume":"39","author":"L. J. Guibas","year":"1989","unstructured":"L. J. Guibas and J. Hershberger. Optimal shortest path queries in a simple polygon. Journal of Computer and System Sciences, 39(2):126\u2013152, Oct. 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"30_CR20","unstructured":"R. H. G\u00fcting. Conquering Contours: Efficient Algorithms for Computational Geometry. PhD thesis, Dortmund, 1983."},{"key":"30_CR21","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1016\/S0734-189X(87)80114-7","volume":"40","author":"R. H. G\u00fctting","year":"1987","unstructured":"R. H. G\u00fctting and T. Ottmann. New algorithms for special cases of hidden line elimination problem. Computer Vision, Graphics, and Image Processing, 40:188\u2013204, 1987.","journal-title":"Computer Vision, Graphics, and Image Processing"},{"key":"30_CR22","doi-asserted-by":"crossref","unstructured":"S. Kapoor and S. N. Maheshwari. Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles. In Proceedings of the Fourth Annual ACM Symposium on Computational Geometry, pages 172\u2013182, 1988.","DOI":"10.1145\/73393.73411"},{"key":"30_CR23","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1002\/net.3230110307","volume":"11","author":"R. C. Larson","year":"1981","unstructured":"R. C. Larson and V. O. Li. Finding minimum rectilinear paths in the presence of barriers. Networks, 11:285\u2013304, 1981.","journal-title":"Networks"},{"issue":"3","key":"30_CR24","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/net.3230140304","volume":"14","author":"D. T. Lee","year":"1984","unstructured":"D. T. Lee and F. P. Preparata. Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14(3):393\u2013410, 1984.","journal-title":"Networks"},{"key":"30_CR25","doi-asserted-by":"crossref","unstructured":"C. E. Leiserson and F. M. Maley. Algorithms for routing and testing routability of planar VLSI layouts. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing, pages 69\u201378, 1985.","DOI":"10.1145\/22145.22153"},{"key":"30_CR26","volume-title":"Topology: A First Course","author":"J. R. Munkres","year":"1975","unstructured":"J. R. Munkres. Topology: A First Course. Prentice-Hall, Englewood Cliffs, N.J., 1975."},{"key":"30_CR27","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry\u2014An Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos. Computational Geometry\u2014An Introduction. Springer-Verlag, New York, 1985."},{"key":"30_CR28","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0890-5401(87)90045-9","volume":"72","author":"G. J. E. Rawlins","year":"1987","unstructured":"G. J. E. Rawlins and D. Wood. Optimal computation of finitely oriented convex hulls. Information and Computation, 72:150\u2013166, 1987.","journal-title":"Information and Computation"},{"key":"30_CR29","unstructured":"J.-R. Sack. Rectilinear Computational Geometry. PhD thesis, Carleton University, 1984."},{"key":"30_CR30","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0734-189X(86)90127-1","volume":"35","author":"S. Suri","year":"1986","unstructured":"S. Suri. A linear time algorithm for minimum link paths inside a simple polygon. Computer Vision, Graphics, and Image Processing, 35:99\u2013110, 1986.","journal-title":"Computer Vision, Graphics, and Image Processing"},{"key":"30_CR31","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0020-0190(91)90189-O","volume":"37","author":"X.-H. Tan","year":"1991","unstructured":"X.-H. Tan, T. Hirata, and Y. Inagaki. The intersection searching problem for c-oriented polygons. Information Processing Letters, 37:201\u2013204, 1991.","journal-title":"Information Processing Letters"},{"key":"30_CR32","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF02187729","volume":"4","author":"G. Toussaint","year":"1989","unstructured":"G. Toussaint. On separating two simple polygons by a single translation. Discrete and Computational Geometry, 4:265\u2013278, 1989.","journal-title":"Discrete and Computational Geometry"},{"key":"30_CR33","first-page":"335","volume-title":"Computational Geometry, volume 2 of Machine Intelligence and Pattern Recognition","author":"G. T. Toussaint","year":"1985","unstructured":"G. T. Toussaint. Movable separability of sets. In G. T. Toussaint, editor, Computational Geometry, volume 2 of Machine Intelligence and Pattern Recognition, pages 335\u2013376. North Holland, Amsterdam, 1985."},{"issue":"2","key":"30_CR34","first-page":"9","volume":"3","author":"G. T. Toussaint","year":"1989","unstructured":"G. T. Toussaint. Computing geodesic properties inside a simple polygon. Revue D'Intelligence Artificielle, 3(2):9\u201342, 1989. Also available as technical report SOCS 88.20, School of Computer Science, McGill University.","journal-title":"Revue D'Intelligence Artificielle"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028273.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:58:41Z","timestamp":1607551121000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028273"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540543430"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/bfb0028273","relation":{},"subject":[]}}