Link distance and shortest path problems in the plane

Agarwal, 2000, Davenport–Schinzel sequences and their geometric applications, 1 A. Aggarwal, H. Booth, J. OʼRourke, S. Suri, C.K. Yap, Finding minimal convex nested polygons, in: 1st Symposium on Computational Geometry (SoCG), 1985, pp. 296–304. Alt, 1995, Computing the Fréchet distance between two polygonal curves, International Journal of Computational Geometry & Applications, 5, 75, 10.1142/S0218195995000064 Alt, 2003, Comparison of distance measures for planar curves, Algorithmica, 38, 45, 10.1007/s00453-003-1042-5 E.M. Arkin, J.S.B. Mitchell, S. Suri, Optimal link path queries in a simple polygon, in: 3rd Symposium on Discrete Algorithms (SODA), 1992, pp. 269–279. B. Aronov, S. Har-Peled, C. Knauer, Y. Wang, C. Wenk, Fréchet distance for curves, revisited, in: 14th Annual European Symposium on Algorithms (ESA), 2006, pp. 52–63. Aurenhammer, 1991, Voronoi diagrams – a survey of a fundamental geometric data structure, ACM Computing Surveys, 23, 345, 10.1145/116873.116880 Bae, 2009, Querying two boundary points for shortest paths in a polygonal domain, vol. 5878, 1054 K. Buchin, M. Buchin, C. Wenk, Computing the Fréchet distance between simple polygons in polynomial time, in: 22nd Symposium on Computational Geometry (SoCG), 2006, pp. 80–87. E.W. Chambers, É. Colin de Verdiére, J. Erickson, S. Lazard, F. Lazarus, S. Thite, Walking your dog in the woods in polynomial time, in: 24th Symposium on Computational Geometry (SoCG), 2008, pp. 101–109. Y. Chiang, J.S.B. Mitchell, Two-point Euclidean shortest path queries in the plane, in: 10th Symposium on Discrete Algorithms (SODA), 1999, pp. 215–224. Cole, 1987, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM, 34, 200, 10.1145/7531.7537 A.F. Cook IV, Obstacle-avoiding similarity metrics and shortest path problems, Dissertation, University of Texas at San Antonio, USA, December 2009. A.F. Cook IV, C. Wenk, Geodesic Fréchet distance inside a simple polygon, in: 25th Symposium on Theoretical Aspects of Computer Science (STACS), 2008. A.F. Cook IV, C. Wenk, Geodesic Fréchet distance with polygonal obstacles, Technical Report CS-TR-2008-010, University of Texas at San Antonio, 2008. A.F. Cook IV, C. Wenk, Min-link shortest path maps and Fréchet distance, Technical Report CS-TR-2008-011, University of Texas at San Antonio, 2008. A.F. Cook IV, C. Wenk, Link distance and shortest path problems in the plane, in: 5th Algorithmic Aspects in Information and Management (AAIM), 2009, pp. 140–151. A. Dumitrescu, G. Rote, On the Fréchet distance of a set of curves, in: 16th Canadian Conference on Computational Geometry (CCCG), 2004, pp. 162–165. A. Efrat, L.J. Guibas, S. Har-Peled, D.C. Lin, J.S.B. Mitchell, T.M. Murali, Sweeping simple polygons with a chain of guards, in: 11th Symposium on Discrete Algorithms (SODA), 2000, pp. 927–936. Efrat, 2002, New similarity measures between polylines with applications to morphing and polygon sweeping, Discrete and Computational Geometry, 28, 535, 10.1007/s00454-002-2886-1 Efrat, 2006, Guarding galleries and terrains, Information Processing Letters, 100, 238, 10.1016/j.ipl.2006.05.014 L. Gewali, A. Meng, J.S.B. Mitchell, S. Ntafos, Path planning in 0/1/∞ weighted regions with applications, in: 4th Symposium on Computational Geometry (SoCG), 1988, pp. 266–278. Ghosh, 1991, An output-sensitive algorithm for computing visibility graphs, SIAM Journal on Computing, 20, 888, 10.1137/0220055 Guibas, 1987, Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons, Algorithmica, 2, 209, 10.1007/BF01840360 Henzinger, 1997, Faster shortest-path algorithms for planar graphs, Journal of Computer and System Sciences, 55, 3, 10.1006/jcss.1997.1493 Hershberger, 1999, An optimal algorithm for Euclidean shortest paths in the plane, SIAM Journal on Computing, 28, 2215, 10.1137/S0097539795289604 Klein, 2009, Abstract Voronoi diagrams revisited, Computational Geometry: Theory & Applications, 42, 885, 10.1016/j.comgeo.2009.03.002 Maheshwari, 2000, Link distance problems, 519 A. Maheshwari, J. Yi, On computing Fréchet distance of two paths on a convex polyhedron, in: 21st European Workshop on Computational Geometry (EuroCG), 2005. Mitchell, 2000, Geometric shortest paths and network optimization, 663 Mitchell, 1992, Minimum-link paths among obstacles in the plane, Algorithmica, 8, 431, 10.1007/BF01758855 Okabe, 2000 G. Rote, Computing the Fréchet distance between piecewise smooth curves, Technical Report ECG-TR-241108-01, May 2005. Suri, 1986, A linear time algorithm for minimum link paths inside a simple polygon, Computer Vision and Graphical Image Processing (CVGIP), 35, 99, 10.1016/0734-189X(86)90127-1 R. van Oostrum, R.C. Veltkamp, Parametric search made practical, in: 18th Symposium on Computational Geometry (SoCG), 2002, pp. 1–9. Wismath, 1992, Computing the full visibility graph of a set of line segments, Information Processing Letters, 42, 257, 10.1016/0020-0190(92)90033-R