The k-Fréchet Distance: How to Walk Your Dog While Teleporting

We introduce a new distance measure for comparing polygonal chains: the k-Fréchet distance. As the name implies, it is closely related to the well-studied Fréchet distance but detects similarities between curves that resemble each other only piecewise. The parameter k denotes the number of subcurves into which we divide the input curves (thus we allow up to k-1 "teleports" on each input curve). The k-Fréchet distance provides a nice transition between (weak) Fréchet distance and Hausdorff distance. However, we show that deciding this distance measure turns out to be NP-hard, which is interesting since both (weak) Fréchet and Hausdorff distance are computable in polynomial time. Nevertheless, we give several possibilities to deal with the hardness of the k-Fréchet distance: besides a short exponential-time algorithm for the general case, we give a polynomial-time algorithm for k=2, i.e., we ask that we subdivide our input curves into two subcurves each. We can also approximate the optimal k by factor 2. We then present a more intricate FPT algorithm using parameters k (the number of allowed subcurves) and z (the number of segments of one curve that intersect the epsilon-neighborhood of a point on the other curve).