2015 | OriginalPaper | Chapter
Straight-Path Queries in Trajectory Data
Authors : Mark de Berg, Ali D. Mehrabi
Published in: WALCOM: Algorithms and Computation
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 +
ε
) algorithm that, given a trajectory
P
and a threshold
τ
, 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
τ
times the length of the edge. This significantly improves the fastest known algorithm for the problem.