Straight-path queries in trajectory data

M.T. Berg, de, A.D. Mehrabi

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
3 Downloads (Pure)


Inspired by sports analysis, we study data structures for storing a trajectory representing the movement of a player during a game, such that the following queries can be answered: Given two positions s and t, report all sub-trajectories in which the player moved in a more or less straight line from s to t. We consider two measures of straightness, namely dilation and direction deviation, and present efficient construction algorithms for our data structures, and analyze their performance. We also present an O(n^{1.5¿+¿e}) algorithm that, given a trajectory P and a threshold t, finds a simplification of P with a minimum number of vertices such that each edge in the simplification replaces a sub-trajectory of length at most t times the length of the edge. This significantly improves the fastest known algorithm for the problem.
Original languageEnglish
Title of host publicationWALCOM: Algorithms and Computation (9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings)
EditorsM.S. Rahman, E. Tomita
Place of PublicationCham
ISBN (Print)978-3-319-15611-8
Publication statusPublished - 2015
Event9th International Workshop on Algorithms and Computation (WALCOM 2015) - Dhaka, Bangladesh
Duration: 26 Feb 201528 Feb 2015
Conference number: 9

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Workshop9th International Workshop on Algorithms and Computation (WALCOM 2015)
Abbreviated titleWALCOM 2015


Dive into the research topics of 'Straight-path queries in trajectory data'. Together they form a unique fingerprint.

Cite this