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

Research output: Contribution to conferenceAbstract

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.
Original languageEnglish
Number of pages8
Publication statusPublished - 16 Mar 2020
Event36th European Workshop on Computational Geometry - Online, Würzburg, Germany
Duration: 16 Mar 202018 Mar 2020
Conference number: 36
https://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/

Conference

Conference36th European Workshop on Computational Geometry
Abbreviated titleEuroCG'20
CountryGermany
CityWürzburg
Period16/03/2018/03/20
Internet address

Keywords

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

Fingerprint Dive into the research topics of 'Fréchet Distance Between Uncertain Trajectories: Computing Expected Value and Upper Bound'. Together they form a unique fingerprint.

Cite this