Central Trajectories

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 $R^1$, where we show that an optimal central trajectory $C$ representing $n$ trajectories, each consisting of $ edges, has complexity $tau n^2)$ and can be computed in $O(tau n^2 log n)$ time. We then consider trajectories in $R^2$, and show that the complexity of $C$ is at most $O(tau n^5/2)$ and can be computed in $O(tau n^3)$ time.