Folding free-space diagrams : computing the Fréchet distance between 1-dimensional curves

By folding the free-space diagram for efficient preprocessing, we show that the Frechet distance between 1D curves can be computed in O(nk log n) time, assuming one curve has ply k.