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.


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.

Slides of the talk   pdf file
other papers about this subject
Last update: October 4, 2016.