  Given two polygonal curves in the plane, there are many ways to define a
notion of similarity between them. One popular measure is the Fr\'echet
distance. Since it was proposed by Alt and Godau in 1992, many variants and
extensions have been studied. Nonetheless, even more than 20 years later, the
original $O(n^2 \log n)$ algorithm by Alt and Godau for computing the Fr\'echet
distance remains the state of the art (here, $n$ denotes the number of edges on
each curve). This has led Helmut Alt to conjecture that the associated decision
problem is 3SUM-hard.
  In recent work, Agarwal et al. show how to break the quadratic barrier for
the discrete version of the Fr\'echet distance, where one considers sequences
of points instead of polygonal curves. Building on their work, we give a
randomized algorithm to compute the Fr\'echet distance between two polygonal
curves in time $O(n^2 \sqrt{\log n}(\log\log n)^{3/2})$ on a pointer machine
and in time $O(n^2(\log\log n)^2)$ on a word RAM. Furthermore, we show that
there exists an algebraic decision tree for the decision problem of depth
$O(n^{2-\varepsilon})$, for some $\varepsilon > 0$. We believe that this
reveals an intriguing new aspect of this well-studied problem. Finally, we show
how to obtain the first subquadratic algorithm for computing the weak Fr\'echet
distance on a word RAM.
