Trajectory grouping structure

DOI10.1007/978-3-642-40104-6_19MaRDI QIDQ2842159zbMATH OpenOpenAlexWikidataFDO

Authors Kevin Buchin, Maike Buchin, Bettina Speckmann, Frank Staals, Marc Van Kreveld

Publication date 12 August 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.6127

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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.

Recommendations

• Trajectory grouping structure
• Trajectory grouping structure under geodesic distance
• A refined definition for groups of moving entities and its computation
• A refined definition for groups of moving entities and its computation
• Central trajectories

Cited in

(8)

• A refined definition for groups of moving entities and its computation
• Reporting flock patterns
• A refined definition for groups of moving entities and its computation
• A family of metrics from the truncated smoothing of Reeb graphs
• Interleaving by parts: join decompositions of interleavings and join-assemblage of geodesics
• Towards the prediction of critical transitions in spatially extended populations with cubical homology
• Trajectory grouping structure under geodesic distance
• Trajectory grouping structure

This page was built for publication: Trajectory grouping structure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2842159)