Finding Complex Patterns in Trajectory Data via Geometric Set Cover

Clustering trajectories is a central challenge when confronted with large amounts of movement data such as full-body motion data or GPS data. We study a clustering problem that can be stated as a geometric set cover problem: Given a polygonal curve of complexity , find the smallest number of representative trajectories of complexity at most such that any point on the input trajectories lies on a subtrajectory of the input that has Fréchet distance at most to one of the representative trajectories. This problem was first studied by Akitaya et al. (2021) and Brüning et al. (2022). They present a bicriteria approximation algorithm that returns a set of curves of size which covers the input with a radius of in time , where is the smallest number of curves of complexity needed to cover the input with a distance of . The representative trajectories computed by their algorithm are always line segments. In applications however, one is usually interested in representative curves of higher complexity which consist of several edges. We present a new approach that builds upon the works of Brüning et al. (2022) computing a set of curves of size in time with the same distance guarantee of , where each curve may consist of curves of complexity up to the given complexity parameter . To validate our approach, we conduct experiments on different types of real world data: high-dimensional full-body motion data and low-dimensional GPS-tracking data.

  • Published in:
  • Type:
  • Authors:
    Conradi, Jacobus; Driemel, Anne
  • Year:

Citation information

Conradi, Jacobus; Driemel, Anne: Finding Complex Patterns in Trajectory Data via Geometric Set Cover, arXiv, 2023,, Conradi.Driemel.2023a,

Associated Lamarr Researchers

lamarr institute person Driemel Anne e1664271117365 - Lamarr Institute for Machine Learning (ML) and Artificial Intelligence (AI)

Prof. Dr. Anne Driemel

Principal Investigator Hybrid ML to the profile