A Representative Curve of k curves with Respect to Frechet Distance

Abstract

This thesis introduces a representative curve for a set of given curves with respect to the Fréchet metric. A representative curve is a curve with the least value of the maximum Fréchet Distance to every curve in the set given. Algorithms to solve the problem are also provided. A decision version of the property is solved first, and the optimization problem is solved by narrowing down the candidates for the decision problem. The time complexity to solve the problem with k curves is O(MlogM), When a convex polygon is given as a constraint, the problem of one and two curves are also discussed.