Fréchet Distance Between Uncertain Trajectories: Computing Expected Value and Upper Bound

A trajectory is a sequence of time-stamped locations. Measurement uncertainty is an important factor to consider when analysing trajectory data. We define an uncertain trajectory as a trajectory where at each time stamp the true location lies within an uncertainty region—a disk, a line segment, or a set of points. In this paper we consider discrete and continuous Fréchet distance between uncertain trajectories.

We show that finding the largest possible discrete or continuous Fréchet distance among all possible realisations of two uncertain trajectories is NP-hard under all the uncertainty models we consider. Furthermore, computing the expected discrete or continuous Fréchet distance is #P-hard when the uncertainty regions are modelled as point sets or line segments. We also study the setting with time bands, where we restrict temporal alignment of the two trajectories, and give polynomial-time algorithms for largest possible and expected discrete and continuous Fréchet distance for uncertainty regions modelled as point sets.