Abstract
A trajectory is a sequence of time-stamped locations, each of which is represented as a point in two or three dimensions. An uncertain trajectory replaces each point, according to some uncertainty model, with a probability distribution, a disk, a set of points, etc. This is used to express uncertainty about the true location of an object and handle measurement imprecision transparently.Fréchet distance is a commonly used trajectory similarity metric, often introduced as the smallest length of a leash needed for a leashed dog and its owner to walk along their two respective trajectories without going backwards.
In this thesis, we discuss similarity of uncertain trajectories, with the focus on region-based uncertainty models (disks, line segments, sets of points) and discrete and continuous Fréchet distance.
We show that finding the upper bound on both the discrete and continuous Fréchet distance on uncertain trajectories is an NP-complete problem in many settings. We also study expected discrete and continuous Fréchet distance, assuming uniform distribution of points within the respective regions, and show that finding it in many settings is #P-hard.
Finally, we discuss the setting with time bands, where we enforce temporal similarity of the two trajectories, thus decreasing the complexity, and give the polynomial-time algorithms to find upper bound and expected value of discrete and continuous Fréchet distance in this setting for trajectories with uncertainty model of sets of points.
| Date of Award | 25 Nov 2019 |
|---|---|
| Original language | English |
| Supervisor | Kevin Buchin (Supervisor 1), Marcel J.M. Roeloffzen (Supervisor 2) & Maarten Löffler (External coach) |