Fr'echet Distance for Curves, Revisited

renewcommandRerm I!hspace-0.025em R newcommandepsvarepsilon newcommandSetXmathsfX newcommandVorX[1]V pth#1 newcommandPolygonmathsfP newcommandSpaceoverlinemathsfm newcommandpth[2][!]#1left(#2right) We revisit the problem of computing Fr'echet distance between polygonal curves under L1, L2, and L_∞ norms, focusing on discrete Fr'echet distance, where only distance between vertices is considered. We develop efficient algorithms for two natural classes of curves. In particular, given two polygonal curves of n vertices each, a eps-approximation of their discrete Fr'echet distance can be computed in roughly O(nkappa3log n/eps3) time in three dimensions, if one of the curves is kappa-bounded. Previously, only a kappa-approximation algorithm was known. If both curves are the so-called backbone~curves, which are widely used to model protein backbones in molecular biology, we can eps-approximate their Fr'echet distance in near linear time in two dimensions, and in roughly O(n4/3log nm) time in three dimensions. In the second part, we propose a pseudo--output-sensitive algorithm for computing Fr'echet distance exactly. The complexity of the algorithm is a function of a quantity we call the emphbwnumber, which is quadratic in the worst case, but tends to be much smaller in practice.