Finding a minimum stretch of a function

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademic

38 Downloads (Pure)


Given a piecewise monotone function f : R ! R and a real value Tmin, we develop an algorithm that finds an interval of length at least Tmin for which the average value of f is minimized. The run-time of the algorithm is linear in the number of monotone pieces of f if certain operations are available in constant time for f. We use this algorithm to solve a basic problem arising in the analysis of trajectories: Finding the most similar subtrajectories of two given trajectories, provided that the duration is at least Tmin. Since the precise solution requires complex operations, we also give a simple (1+")approximation algorithm in which these operations are not needed.
Originele taal-2Engels
TitelAbstracts 25th European Workshop on Computational Geometry (EuroCG'09, Brussels, Belgium, March 16-18, 2009)
StatusGepubliceerd - 2009


Duik in de onderzoeksthema's van 'Finding a minimum stretch of a function'. Samen vormen ze een unieke vingerafdruk.

Citeer dit