Lexicographic Fréchet matchings

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.