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