Semi-computability of the Fréchet distance between surfaces, Proc. 21st European Workshop on Computational Geometry, pp.45-48, 2005. ,
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. ,
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
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
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
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
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. ,
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
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
An Optimal Algorithm for Euclidean Shortest Paths in the Plane, SIAM Journal on Computing, vol.28, issue.6 ,
DOI : 10.1137/S0097539795289604
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. ,
On computing Fréchet distance of two paths on a convex polyhedron, Proc. 21st European Workshop on Computational Geometry, pp.41-44, 2005. ,
The Nature and Meaning of Perturbations in Geometric Computing, Discrete & Computational Geometry, vol.19, issue.1, pp.1-1775, 1998. ,
DOI : 10.1007/PL00009330
For all integers i and j, the restriction of d h to any grid cell C i,j is convex ,
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 ,