Central Trajectories

Abstract

An important task in trajectory analysis is clustering. The results of a clustering are often summarized by a single representative trajectory and an associated size of each cluster. We study the problem of computing a suitable representative of a set of similar trajectories. To this end we define a central trajectory $\mathcal{C}$, 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 $\mathcal{C}(t)$ is as central as possible. We measure centrality in terms of the radius of the smallest disk centered at $\mathcal{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 ${\mathbb{R}}^1$, where we show that an optimal central trajectory $\mathcal{C}$ representing $n$ trajectories, each consisting of $\tau$ edges, has complexity $\Theta (\tau n^2)$ and can be computed in $O(\tau n^2\log n)$ time. We then consider trajectories in ${\mathbb{R}}^d$ with $d\ge 2$, and show that the complexity of $\mathcal{C}$ is at most $O(\tau n^{5/2})$ and can be computed in $O(\tau n^3)$ time.

Full version