Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time (Q1037652)

Computing the distance between two sets (say two curves) is a problem appearing in different applicable situations. One possibility is using the Hausdorff distance. This paper deals with a different distance, namely Fréchet distance, between plane curves. This distance, also called dogleash-distance, is defined as the minimum length of a leash required to connect a dog and its owner as they walk without backtracking along their respective curves from one endpoint to the other; in the introduction of the paper the authors quote some references for illustrating the applicability of this type of distance. In this paper, the authors present a generalization of the Fréchet distance requiring continuity on the motion of the leash. In addition, they present a polynomial time algorithm for computing this generalized distance between two polygonal curves in the plane minus a set of polygonal obstacles.