slides
An important task in trajectory analysis is clustering. The results of a clustering are often given by a single representative trajectory for each cluster. We study the problem of computing a suitable representative. We define a central trajectory, which consists of pieces of the input trajectories, switches from one entity to another only if they are within a small distance of each other, and such that at any time t, the point C(t) is as central as possible. We measure centrality in terms of the radius of the smallest disk centred at C(t) enclosing all entities at time t, and discuss how the techniques can be adapted to other measures of centrality. We first study the problem in ℝ1, where we show that an optimal central trajectory C representing n trajectories, each consisting of τ edges, has complexity Θ(τn2) and can be computed in O(τn2logn) time. We then consider trajectories in ℝ2, and show that the complexity of C is at most O(τn5/2) and can be computed in O(τn3) time.