For a metric space $Y$, the Frechet distance is a metric on trajectories $f,g:[0,1]\to Y$ that minimizes $\max_{t\in [0,1]}d_Y(f(t), g(h(t)))$ over continuous reparameterizations $h$ of time. One can define the generalized Frechet distance between more complex objects, functions $f:X\to Y$ where $X$ is some topological space that minimizes over homeomorphisms from $X\to X$. This more general definition has been studied for surfaces and often leads to computationally hard problems. We show how to compute in polynomial-time signatures for these functions for which the resulting metric on the signatures can also be computed in polynomial-time and provides a meaningful lower bound on the generalized Frechet distance. Our approach uses persistent homology and exploits the natural invariance of persistence diagrams of functions to homeomorphisms of the domain. Our algorithm for computing the signatures in Euclidean spaces uses a new method for computing persistent homology of convex functions on simplicial complexes which may be of independent interest.

@inproceedings{sheehy18frechet,
  Author = {Donald R. Sheehy},
  Booktitle = {Proceedings of the ACM-SIAM Symposium on Discrete Algorithms},
  Title = {Fr\'{e}chet-Stable Signatures Using Persistence Homology},
  Pages = {1100--1108},
  Year = {2018}}