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 \(\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 \geq 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.
@article{central2017, author = {Van Kreveld, Marc and L{\"o}ffler, Maarten and Staals, Frank}, title = {Central Trajectories}, journal = {Journal of Computational Geometry}, category = {trajectories}, year = {2017}, doi = {10.20382/jocg.v8i1a14}, url = {https://dx.doi.org/10.20382/jocg.v8i1a14}, pages = {366--386}, numpages = {21}, volume = {8}, number = {1}, }
@article{central_eurocg2015, author = {Van Kreveld, Marc and L{\"o}ffler, Maarten and Staals, Frank}, title = {Central Trajectories}, journal = {Abstr. 31th European Workshop on Computational Geometry (EuroCG)}, year = {2015}, location = {Ljubljana, Slovenia}, numpages = {4}, pages = {129 -- 132}, url = {http://eurocg15.fri.uni-lj.si/pub/eurocg15-book-of-abstracts.pdf}, category = {trajectories}, project = {central2017}, }