Before revision:  (1) a linear-time algorithm for deciding the Fr\'echet distance between two curves, (2) an algorithm that computes the  \ in O((n+m)\log (n+m)) time, (3) a linear-time d-approximation algorithm, and (4) a data structure that supports O(m\log^2 n)-time decision queries, where m is the number of vertices of the query curve and n the number of vertices of the preprocessed curve.
After revision:  (1) a linear-time algorithm for deciding the Fr\'echet distance between two curves, (2) an algorithm that computes the  Fr\'echet distance in O((n+m)\log (n+m)) time, (3) a linear-time d-approximation algorithm, and (4) a data structure that supports O(m\log^2 n)-time decision queries, where m is the number of vertices of the query curve and n the number of vertices of the preprocessed curve.