I am assistant professor (UD) in the Data Mining group at the Eindhoven University of Technology. I have a broad interest in high-dimensional algorithmic problems involving geometry, motivated by applications in geographic information science and data analysis. I am particularly interested in curve and graph similarity computations---be it mapping trajectories to road networks or clustering time series.
In this thesis we apply a toolkit called realistic analysis to open problems in the areas of computational geometry and geographic information science.
We first study the Fréchet distance, a similarity measure for outlines of shapes or paths of moving objects. Under a new realistic input model, we can approximate the Fréchet distance in near-linear time, where previous algorithms run in quadratic time. We extend our algorithm to a sophisticated variant, the shortcut Fréchet distance, which captures partial similarity. We show that this new variant is NP-hard to compute in general. Along the way, we develop data structures to support Fréchet-distance queries.
In the second part of the thesis, we study computations on digital terrain models. We develop a theory that enables fuzzy hydrological computations when elevation data is imprecise. We show that, under realistic assumptions, geodesic Voronoi diagrams have linear complexity.