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

keywords: Computational Geometry, Geographical Information Analysis, Trajectories

### Journal Article (peer-reviewed)

Frank Staals, Maarten Löffler, Marc van Kreveld

Central Trajectories

Journal of Computational Geometry

8, 1, 366–386, 2017

### Workshop or Poster (weakly reviewed)

Frank Staals, Maarten Löffler, Marc van Kreveld

Central Trajectories

Proc. 31st European Workshop on Computational Geometry

129–132, 2015

back to list