Trajectory Grouping Structure

Abstract

The collective motion of a set of moving entities like people, birds, or other animals, is characterized by groups arising, merging, splitting, and ending. Given the trajectories of these entities, we define and model a structure that captures all of such changes using the Reeb graph, a concept from topology. The trajectory grouping structure has three natural parameters that allow more global views of the data in group size, group duration, and entity inter-distance. We prove complexity bounds on the maximum number of maximal groups that can be present, and give algorithms to compute the grouping structure efficiently. We also study how the trajectory grouping structure can be made robust, that is, how brief interruptions of groups can be disregarded in the global structure, adding a notion of persistence to the structure. Furthermore, we showcase the results of experiments using data generated by the NetLogo flocking model and from the Starkey project. The Starkey data describe the movement of elk, deer, and cattle. Although there is no ground truth for the grouping structure in this data, the experiments show that the trajectory grouping structure is plausible and has the desired effects when changing the essential parameters. Our research provides the first complete study of trajectory group evolvement, including combinatorial, algorithmic, and experimental results.

Corresponding Publications

Trajectory Grouping Structure

Kevin Buchin, Maike Buchin, Marc van Kreveld, Bettina Speckmann, Frank Staals

Proc. 2013 WADS Algorithms and Data Structures Symposium, 2013

@incollection{grouping2013,
  author = {Buchin, Kevin and Buchin, Maike and
                van Kreveld, Marc and Speckmann, Bettina and Staals, Frank},
  title = {Trajectory Grouping Structure},
  booktitle = {Proc. 2013 WADS Algorithms and Data Structures Symposium},
  series = {LNCS},
  year = {2013},
  volume = {8037},
  location = {London, Ontario, Canada},
  numpages = {12},
  publisher = {Springer},
  pages = {219--230},
  url = {https://dx.doi.org/10.1007/978-3-642-40104-6_19},
  doi = {10.1007/978-3-642-40104-6_19},
  category = {trajectories},
}

Trajectory Grouping Structure

Kevin Buchin, Maike Buchin, Marc van Kreveld, Bettina Speckmann, Frank Staals

Journal of Computational Geometry, 2015

@article{grouping2015,
  author = {Buchin, Kevin and Buchin, Maike and
                van Kreveld, Marc and Speckmann, Bettina and Staals, Frank},
  title = {Trajectory Grouping Structure},
  journal = {Journal of Computational Geometry},
  category = {trajectories},
  year = {2015},
  project = {grouping2013},
  volume = {6},
  number = {1},
  doi = {10.20382/jocg.v6i1a3},
  url = {https://dx.doi.org/10.20382/jocg.v6i1a3},
}