Trajectory grouping structure

K. Buchin, M. Buchin, M.J. Kreveld, van, B. Speckmann, F. Staals

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

17 Citaten (Scopus)


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, namely group size, group duration, and entity inter-distance. These parameters allow us to obtain detailed or global views of the data. We prove complexity bounds on the maximum number of maximal groups that can be present, and give algorithms to compute the grouping structure efficiently. Furthermore, we showcase the results of experiments using data generated by the NetLogo flocking model and from the Starkey project. Although there is no ground truth for the groups 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.
Originele taal-2Engels
TitelAlgorithms and Data Structures (13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings)
RedacteurenF. Dehne, R. Solis-Orba, J.-R. Sack
Plaats van productieBerlin
ISBN van geprinte versie978-3-642-40103-9
StatusGepubliceerd - 2013

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743

Vingerafdruk Duik in de onderzoeksthema's van 'Trajectory grouping structure'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Buchin, K., Buchin, M., Kreveld, van, M. J., Speckmann, B., & Staals, F. (2013). Trajectory grouping structure. In F. Dehne, R. Solis-Orba, & J-R. Sack (editors), Algorithms and Data Structures (13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings) (blz. 219-230). (Lecture Notes in Computer Science; Vol. 8037). Springer.