  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.

Computational Geometry