The k-Fréchet distance
share
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. 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-complete, 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 an 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 also present an approximation algorithm that outputs a number of subcurves of at most twice the optimal size. Finally, we give an FPT algorithm using parameters k (the number of allowed subcurves) and z (the number of segments of one curve that intersects the ε-neighborhood of a point on the other curve).
READ FULL TEXT