# 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 $$\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.

## Corresponding Publications

• ### Central Trajectories

Journal of Computational Geometry, 2017
@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},
}

• ### Central Trajectories

Abstr. 31th European Workshop on Computational Geometry (EuroCG), 2015
@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},
}