Geometry Seminar

---

The Fréchet Distance Unleashed: Approximating a Dog with a Frog

Speaker: Sariel Har-Peled, University of Illinois

Location: Online Zoom-only

Videoconference link: https://youtu.be/x3ouud_KOw0

Date: Tuesday, October 1, 2024, 2 p.m.

Synopsis:

We show that a minor variant of the continuous Fréchet distance between polygonal curves can be computed using essentially the same algorithm used to solve the discrete version, thus dramatically simplifying the algorithm for computing it. The new variant is not necessarily monotone, but this shortcoming can be easily handled via refinement. Combined with a Dijkstra/Prim type algorithm, this leads to a realization of the Fréchet distance (i.e., a morphing) that is locally optimal (aka locally correct), that is both easy to compute, and in practice, takes near linear time on many inputs. The new morphing has the property that the leash is always as short-as-possible. We implemented the new algorithm, and developed various strategies to get a fast execution in practice. Among our new contributions is a new simplification strategy that is distance-sensitive, and enables us to compute the exact continuous Fréchet distance in near linear time in practice. We performed extensive experiments on our new algorithm, and released Julia and Python packages with these new implementations.

Paper is available on arXiv: https://arxiv.org/abs/2407.03101

The animations for the paper are here: https://frechet.xyz/

Notes:

Contact Boris Aronov to be placed on the mailing list with noticafitions and Zoom seminar info.