Enhancing geometric algorithms with uncertainty models

Kevin Buchin, Associate Professor in the Algorithms research group, received an NWO TOP C2 grant for starting a new research project on geometric algorithms. The goal of the project is to develop the theoretical foundation for integrating uncertainty models with geometric algorithms. A PhD student will be appointed in due time to work on this project.

Advances in tracking technology have resulted in an explosion of movement data being recorded for research, industry, and everyday life. Analyzing this data has many applications: sports coaches want to analyze game patterns, biologists want to understand the movement behavior of animals, and shop owners want to know how customers move through their store.

The current methods for analyzing movement data make very unrealistic assumptions about the relationship between the measured data and the actual route that has been taken. They assume that the measured locations are completely accurate and that the part of the route between two successive measuring points is a straight line. There are three major problems with these assumptions.

First, GPS and other technologies for measuring locations are often not very precise. Secondly, in many applications (for example when animals are monitored using small GPS devices) the time between successive measuring points is large. This has the advantage that a longer time can be measured, but a consequence is that the distance traveled between successive measuring points is no longer a straight line. Thirdly, in some applications it is important to monitor the use of space over time, for example the habitat of a group of animals. This leads to the study of moving areas instead of moving points.

In this research project, Kevin Buchin will develop algorithms for analyzing movement data that take into account the above aspects. As a result, much more reliable conclusions can be drawn than has been the case until now.