Geometric Algorithms for Trajectory Analysis

Abstract

Technology such as the Global Positing System (GPS) has made tracking moving entities easy and cheap. As a result there is a large amount of trajectory data available, and an increasing demand on tools and techniques to analyze such data. We consider several analysis tasks for trajectory data, and develop efficient algorithms to perform them automatically. In particular, we study the following tasks: •Find a segmentation of a trajectory based on a non-monotone criterion. •Find hotspots; regions in which the entity spent a large amount of time. •Find all groups and the grouping structure. A group is a movement pattern in which sufficiently many entities move together during a sufficiently long time interval. In addition to the groups themselves we also find the relation between groups, e.g. a large group came into existence when two smaller groups merged. •Find a central trajectory: a representative for a set of trajectories.

For each task, we formalize the problem, and analyze its geometric properties. We use these properties to obtain efficient algorithms to automatically perform the task at hand. In many cases, we also show that our analysis is tight, and that our algorithms are optimal.