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

Onderzoeksoutput: Bijdrage aan congresAbstract

Samenvatting

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.
Originele taal-2Engels
Aantal pagina's8
StatusGepubliceerd - 16 mrt 2020
Evenement36th European Workshop on Computational Geometry - Online, Würzburg, Duitsland
Duur: 16 mrt 202018 mrt 2020
Congresnummer: 36
https://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/

Congres

Congres36th European Workshop on Computational Geometry
Verkorte titelEuroCG'20
LandDuitsland
StadWürzburg
Periode16/03/2018/03/20
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Fréchet Distance Between Uncertain Trajectories: Computing Expected Value and Upper Bound'. Samen vormen ze een unieke vingerafdruk.

Citeer dit