Frechet distance for curves, revisited

We revisit the problem of computing the Frechet distance between polygonal curves, focusing on the discrete Frechet distance, where only distance between vertices is considered. We develop efficient approximation algorithms for two natural classes of curves: kappa-bounded curves and backbone curves, the latter of which are widely used to model molecular structures. We also propose a pseudo-output-sensitive algorithm for computing the discrete Frechet distance exactly. The complexity of the algorithm is a function of the complexity of the free-space boundary, which is quadratic in the worst case, but tends to be lower in practice.