Abstract : We consider clustering problems that are fundamental when dealing with trajectory and time series data. The Fréchet distance provides a natural way to measure similarity of curves under continuous reparametrizations. Applied to trajectories and time series, it has proven to be very versatile as it allows local non-linear deformations in time and space. Subtrajectory clustering is a variant of the trajectory clustering problem, where the start and endpoints of trajectory patterns within the collected trajectory data are not known in advance. We study this problem in the form of a set cover problem for a given polygonal curve: find the smallest number k of representative curves such that any point on the input curve is contained in a subcurve that has Fréchet distance at most a given r to a representative curve.

Keywords : clustering of trajectories; Fréchet distance; set cover problem