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.