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

Marc Van Kreveld, Maarten Löffler, Frank Staals

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

Marc Van Kreveld, Maarten Löffler, Frank Staals

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},
}