Finding long and similar parts of trajectories

A natural time-dependent similarity measure for two trajectories is their average distance at corresponding times. We give algorithms for computing the most similar subtrajectories under this measure, assuming the two trajectories are given as two polygonal, possibly self-intersecting lines with time stamps. For the case when a minimum duration of the subtrajectories is specified and the subtrajectories must start at corresponding times, we give a linear-time algorithm. The algorithm is based on a result of independent interest: We present a linear-time algorithm to find, for a piece-wise monotone function, an interval of at least a given length that has minimum average value. In the case that the subtrajectories may start at non-corresponding times, it appears difficult to give exact algorithms, even if the duration of the subtrajectories is fixed. For this case, we give (1+ε)-approximation algorithms, for both fixed duration and when only a minimum duration is specified.