Folding Free-Space Diagrams

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.