Anne Driemel, University of Bonn

Abstract

I consider two algorithmic problems that are fundamental when dealing with curves in the form of trajectory and time series data: clustering and proximity searching. The Fréchet distance provides a natural way to measure the similarity of curves under varying continuous reparametrizations. However, its mathematical simplicity disguises its computational complexity since it does not naturally behave like a doubling space. I will give a brief overview of recent data structure techniques for different variants of proximity searching under the Fréchet distance. The input is a set of polygonal curves and the query is a polygonal curve and should return the input curves that are closest to the query curve.