We revisit the problem of computing the Fréchet distance between polygonal curves, focusing on the
Fréchet distance, where only distance between vertices is considered. We develop efficient approximation algorithms for two natural classes of curves:
curves, the latter of which are widely used to model molecular structures. We also propose a pseudo–output-sensitive algorithm for computing the discrete Fréchet 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.