## Abstract

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.

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.

Original language | English |
---|---|

Number of pages | 8 |

Publication status | Published - 16 Mar 2020 |

Event | 36th European Workshop on Computational Geometry - Online, Würzburg, Germany Duration: 16 Mar 2020 → 18 Mar 2020 Conference number: 36 https://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/ |

### Conference

Conference | 36th European Workshop on Computational Geometry |
---|---|

Abbreviated title | EuroCG'20 |

Country/Territory | Germany |

City | Würzburg |

Period | 16/03/20 → 18/03/20 |

Internet address |

## Keywords

- uncertainty
- trajectories
- Fréchet distance
- #P hardness
- time bands