Middle curves based on discrete Fréchet distance

Abstract Given a set of polygonal curves, we present algorithms for computing a middle curve that serves as a representative for the entire set of curves. We require that the middle curve consists of vertices of the input curves and that it minimizes the maximum discrete Frechet distance to all input curves. We consider three different variants of a middle curve depending on in which order vertices of the input curves may occur on the middle curve, and provide algorithms for computing each variant.