Efficient Approximation Algorithms for the Fréchet Distance

The Fréchet distance is a popular similarity measure for curves and surfaces that captures their continuous nature well. Various aspects and variants of the Fréchet distance have been studied in depth by the scientific community. Yet, the most fundamental question still remains unsolved: how fast can one compute the Fréchet distance between two polygonal curves? While near-quadratic time algorithms exist, there is strong evidence that one cannot do much better in the most general setting. In this thesis we present several approximation algorithms with subquadratic running times. Additionally, we show that in a restricted setting we can compute the Fréchet distance exactly and in subquadratic time. For arbitrary curves in general dimensions, we present a trade-off between approximation error and running time. We achieve subquadratic running times by developing a new curve simplification algorithm. The result is the first strongly-subquadratic time approximation algorithm with an arbitrarily small polynomial approximation error. We also consider curves in the plane, with the additional property that the curves bound a simple polygon. Rather than measuring distances by the straight-line (Euclidean) distance, we measure distances as lengths of shortest paths in the polygon. We give a near-linear time approximation scheme for this variant of the Fréchet distance. This result improves upon an existing near-linear time 2-approximation algorithm. We further investigate the setting where the curves bound a polygon, using another natural metric to measure distances between points. Specifically, we show that if distances are measured by the lengths of shortest rectilinear paths in the polygon, we can compute the Fréchet distance exactly and in near-linear time. Lastly, we study an application of the Fréchet distance to subtrajectory clustering. Here, the goal is to identify patterns in a given input curve (trajectory). Formally, given some target distance, the goal is to cluster subcurves that have Fréchet distance at most the target distance to some (to be determined) low complexity curve (the pattern). The aim is to cover the input curve with as few clusters as possible. We approximate both the target distance and the number of clusters. Our algorithm is deterministic and improves upon previous work with respect to the error in distance, the running time, and the space usage.