## Günter Rote:

# Lexicographic Fréchet matchings (extended abstract)

In: *Abstracts of the 30th European Workshop on Computational Geometry*
(EuroCG'14), Ein-Gedi, Israel, March 2014, Editors: Paz Carmi, Matthew Katz,
and Shakhar Smorodinsky, 4 pages.
### Abstract

The Fréchet distance between two curves is the maximum distance in a
simultaneous traversal of the two curves. We refine this notion by not only
looking at the maximum distance but at all other distances. Roughly speaking,
we want to minimize the time `T`(`s`)
during which the distance exceeds
a threshold `s`, subject to upper speed constraints. We optimize these
times lexicographically, giving more weight to larger distances `s`.
For polygonal curves in general position, this criterion produces a unique
monotone matching between the points on the two curves, which is important
for applications like morphing, and we can compute this matching in polynomial
time.

Last update: October 4, 2016.