H. Alt and M. Buchin, Semi-computability of the Fréchet distance between surfaces, Proc. 21st European Workshop on Computational Geometry, pp.45-48, 2005.

H. Alt and M. Godau, Computing the Fréchet distance between two polygonal curves Sorting in c log n parallel steps, AKS83] Miklós Ajtai, János Komlós, and Endre Szemerédi, pp.75-911, 1983.

S. Bespamyatnikh, Computing homotopic shortest paths in the plane, Proc. 14th Annu. ACM-SIAM Sympos. Discrete Algorithms, pp.609-617, 2003.
DOI : 10.1016/S0196-6774(03)00090-7

S. Bespamyatnikh, Encoding Homotopy of Paths in the Plane, Proc. LATIN 2004: Theoretical Infomatics, pp.329-338, 2004.
DOI : 10.1007/978-3-540-24698-5_37

B. Chazelle, A theorem on polygon cutting with applications, 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pp.339-349, 1982.
DOI : 10.1109/SFCS.1982.58

S. Cabello, Y. Liu, A. Mantler, and J. Snoeyink, Testing Homotopy for Paths in the Plane, Discrete and Computational Geometry, vol.31, issue.1, pp.61-81, 2004.
DOI : 10.1007/s00454-003-2949-y

R. C. , J. S. Mitchell, and T. M. Murali, Geodesic Fréchet and Hausdorff distance inside a simple polygon New similarity measures between polylines with applications to morphing and polygon sweeping, Slowing down sorting networks to obtain faster sorting algorithms. JACMCW07] Altas Cook and Carola Wenk, pp.200-208535, 1987.

A. Efrat, S. G. Kobourov, and A. Lubiw, Computing homotopic shortest paths efficiently, Proc. Internat. Sympos. Symbolic and Algebraic Computation, pp.162-172, 1998.
DOI : 10.1016/j.comgeo.2006.03.003

URL : http://doi.org/10.1016/j.comgeo.2006.03.003

J. Hershberger and J. Snoeyink, Computing minimum length paths of a given homotopy class, Computational Geometry, vol.4, issue.2, pp.63-67, 1994.
DOI : 10.1016/0925-7721(94)90010-8

J. Hershberger and S. Suri, An Optimal Algorithm for Euclidean Shortest Paths in the Plane, SIAM Journal on Computing, vol.28, issue.6
DOI : 10.1137/S0097539795289604

S. J. Comput-[-lp84-]-d, F. P. Lee, and . Preparata, Euclidean shortest paths in the presence of rectilinear barriers. Networks Applying parallel computation algorithms in the design of serial algorithms, J. ACM, vol.28, issue.30, pp.2215-2256393, 1983.

A. Maheshwari and J. Yi, On computing Fréchet distance of two paths on a convex polyhedron, Proc. 21st European Workshop on Computational Geometry, pp.41-44, 2005.

R. Seidel, The Nature and Meaning of Perturbations in Geometric Computing, Discrete & Computational Geometry, vol.19, issue.1, pp.1-1775, 1998.
DOI : 10.1007/PL00009330

A. Corollary, For all integers i and j, the restriction of d h to any grid cell C i,j is convex

E. Wolf and C. , mail address: erinwolf@uiuc E-mail address: Eric.Colin.de.Verdiere@ens.fr Jeff Erickson, Department of Computer Science, University of Illinois at Urbana-Champaign, USA E-mail address: jeffe@cs.uiuc E-mail address: lazard@loria, E-mail address: Francis.Lazarus@lis.inpg.fr Shripad Thite, Center for the Mathematics of Information, California Institute of Technology, USA E-mail address: sthite@win.tue.nl