Finding long and similar parts of trajectories

K. Buchin, M. Buchin, M.J. Kreveld, van, J. Luo

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

36 Citaten (Scopus)

Samenvatting

A natural time-dependent similarity measure for two trajectories is their average distance at corresponding times. We give algorithms for computing the most similar subtrajectories under this measure, assuming the two trajectories are given as two polygonal, possibly self-intersecting lines with time stamps. For the case when a minimum duration of the subtrajectories is specified and the subtrajectories must start at corresponding times, we give a linear-time algorithm. The algorithm is based on a result of independent interest: We present a linear-time algorithm to find, for a piece-wise monotone function, an interval of at least a given length that has minimum average value. In the case that the subtrajectories may start at non-corresponding times, it appears difficult to give exact algorithms, even if the duration of the subtrajectories is fixed. For this case, we give (1+e)-approximation algorithms, for both fixed duration and when only a minimum duration is specified. Keywords: Trajectory analysis; Similarity measure; Moving objects
Originele taal-2Engels
Pagina's (van-tot)465-476
TijdschriftComputational Geometry
Volume44
Nummer van het tijdschrift9
DOI's
StatusGepubliceerd - 2011

Vingerafdruk

Duik in de onderzoeksthema's van 'Finding long and similar parts of trajectories'. Samen vormen ze een unieke vingerafdruk.

Citeer dit