Group diagrams for representing trajectories

ABSTRACT

Given the trajectories of one or several moving groups, we propose a new framework, the group diagram (GD) for representing these. Specifically, we seek a minimal GD as a concise representation of the groups maintaining the spatio-temporal structure of the groups’ movement. A GD is specified by three input values, namely a distance threshold, a similarity measure and a minimality criterion. For several variants of the GD, we give a comprehensive analysis of their computational complexity and present efficient approximation algorithms for their computation. Furthermore, we experimentally evaluate our algorithms on GPS data of migrating geese. Applying the proposed methods on these data sets reveals how the GD concisely represents the movement of the groups. This representation can be used for further analysis and for the formulation of new hypotheses for further ecological research, such as differences in movement patterns of groups on different surfaces or the shift of migration routes over several years. We use different similarity measures to summarize the migration routes of (i) a goose family for one migration period and to summarize (ii) the migration routes of one individual for several migration periods or (iii) the migration routes of several independent individuals for one migration period.

KEYWORDS:

• Movement analysis
• trajectory analysis
• computational geometry
• Fréchet distance
• equal-time distance

Acknowledgments

We are grateful to Gerard Müskens and the Dutch Association of Goose Catcher for help with catching and tagging goose families. AK acknowledges funding from the DLR (ICARUS directive).

Disclosure statement

No potential conflict of interest was reported by the authors.

Data and codes availability statement

The data and codes that support the findings of this study are available on Zenodo with the identifier 10.5281/zenodo.3508780.

Additional information

Funding

This work was supported by the Deutsche Forschungsgemeinschaft (DFG) [BU 2419/3-1].

Notes on contributors

Maike Buchin

Maike Buchin is a professor at the Ruhr University in Bochum, Germany. Her research interests are algorithms and computational complexity of geometric problems, in particular problems arising in movement analysis.

Bernhard Kilgus

Bernhard Kilgus is a PhD student in the Department of Mathematics at the Ruhr University in Bochum, Germany. His research activity focuses on geometric algorithms, in particular algorithms for movement analysis.

Andrea Kölzsch

Andrea Kölzsch is a Postdoctoral Researcher at the Max Planck Institute for Animal Behavior in Radolfzell, Germany. Her research focuses on the ecology and behaviour of migratory Arctic geese under global change, for which she uses high-resolution GPS tracking and remote sensing.