BARC Talks by Carolin Rehs and Kevin Buchin: Oriented Spanners & Uncertain Points and Trajectories

Carolin Rehs: Oriented Spanners

Given a point set P in the Euclidean plane and a parameter t, we define an oriented t-spanner as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest cycle in G through those points is at most a factor t longer than the shortest oriented cycle in the complete bi-directed graph. We investigate the problem of computing sparse graphs with small oriented dilation. As we can show that minimising oriented dilation for a given number of edges is NP-hard in the plane, we first consider one-dimensional point sets and then expand the results to two-dimensional convex point sets. 

Kevin Buchin: Uncertain Points and Trajectories

Location data often comes with some error. For instance, the measurements might be imprecise, or the exact location might be obfuscated to preserve privacy. Nonetheless, most algorithms treat these data as if the exact locations are known. The computational geometry of uncertain points is about designing algorithms that deal with the uncertainty explicitly. In my talk, I will first present how uncertain points are commonly modeled and give an overview of algorithmic results on uncertain points for a variety of geometric problems. Then I will focus on uncertain trajectories and discuss in particular the problem of computing the Frechet distance between uncertain curves.

Carolin and Kevin will be visiting BARC from Monday the 18th, hosted by Mikkel Abrahamsen - please don't hesitate to get in touch!