KAIST Discrete Math Seminar

In shape matching, we are given two geometric objects and we compute their distance according to some geometric similarity measure. The Fréchet distance is a natural distance function for continuous shapes such as curves and surfaces, and is defined using reparameterizations of the shapes.

The discrete Fréchet distance is a variant of the Fréchet distance in which we only consider vertices of polygonal curves. In this talk, we consider the problem of computing the discrete Fréchet distance between two polygonal curves when their vertices are imprecise, and describe efficient algorithms for the problem.