Before revision:  We prove four main results for the case when all edges of both curves are long compared to the Fr\'echet distance between them: (1) a linear-time algorithm for deciding the Fr\'echet distance between two curves, (2) an algorithm that computes the Fr\'echet distance \Frd in O((n+m)\log (n+m)) time, (3) a linear-time d -
After revision:  We prove four results for the case when all edges of both curves are long compared to the Fr\'echet distance between them: (1) a linear-time algorithm for deciding the Fr\'echet distance between two curves, (2) an algorithm that computes the Fr\'echet distance \Frd in O((n+m)\log (n+m)) time, (3) a linear-time d -