Maike Buchin, Ruhr-Universität Bochum

Raum SR006

11:30 - 12:00 Lehrprobe k-Median Problem

12:00 - 12:45 Model-based classification of trajectories

First I will give a brief introduction to my research interests in the

field of computational geometry, in particular shape matching and

algorithms for geographic data. Then I will talk about a specific

problem in analysing trajectory data. Data collected by moving objects,

such as cars, animals, or people, are becoming more and more common. To

analyze large amounts of such trajectory data requires efficient

algorithms. Here we will consider the task of classifying this data,

i.e., grouping trajectories such that they have similar movement

characteristics. Our approach is based on a movement model parameterized

by a single parameter, like the Brownian bridge movement model. We

define an optimal classification to be one that minimizes an information

criterion balancing the likelihood of the model and its size. We give an

efficient algorithm to compute the optimal classification for a discrete

set of parameter values. For continuous parameters the problem becomes

NP-hard. But we also present an algorithm that solves the problem in

polynomial time under mild assumptions on the input.