Fast Algorithms for Fréchet-Based Similarity

Abstract

Polygonal curves arise naturally when recording movement data from GPS traces, animal tracking, or eye-gaze measurements. A fundamental task is to compare such curves using a formal notion of similarity. The Fréchet distance is a widely used metric for this purpose, as it respects both the geometric proximity and the traversal order of two curves. This thesis develops faster algorithms for four Fréchet-based similarity problems, each using the freespace diagram as its central tool.

In Chapter 2, we study the Fréchet distance under geometric transformations, which is essential when comparing shapes regardless of their position or orientation. We present the first improvement to the decision problem for a wide class of transformations, including translations, rotations, and scalings.

In Chapter 3, we consider the Fréchet edit distance, which allows inserting or deleting vertices before measuring the continuous Fréchet distance. This variant is motivated by the need for robustness against outliers and noise in real-world trajectory data. We provide faster algorithms for several edit models, improving on prior bounds by up to a factor of k · n.

In Chapter 4, we study subtrajectory clustering on c-packed trajectories, a realistic model of movement data with bounded self-overlap. We present a near-linear time approximation algorithm for the subtrajectory cluster problem, circumventing the conditional cubic lower bound for general curves.

In Chapter 5, we connect the partial weak Fréchet similarity to shortest paths in weighted planar regions. We construct a near-linear size approximate spanner for the 0/1/∞ weighted region problem, and apply it to obtain an approximation algorithm for the partial weak Fréchet similarity.