  Measuring the similarity of curves is a fundamental problem arising in many
application fields. There has been considerable interest in several such
measures, both in Euclidean space and in more general setting such as curves on
Riemannian surfaces or curves in the plane minus a set of obstacles. However,
so far, efficiently computable similarity measures for curves on general
surfaces remain elusive. This paper aims at developing a natural curve
similarity measure that can be easily extended and computed for curves on
general orientable 2-manifolds. Specifically, we measure similarity between
homotopic curves based on how hard it is to deform one curve into the other one
continuously, and define this "hardness" as the minimum possible surface area
swept by a homotopy between the curves. We consider cases where curves are
embedded in the plane or on a triangulated orientable surface with genus $g$,
and we present efficient algorithms (which are either quadratic or near linear
time, depending on the setting) for both cases.
