2015 | OriginalPaper | Buchkapitel
Straight-Path Queries in Trajectory Data
Autoren: Mark de Berg, Ali D. Mehrabi
Verlag: Springer International Publishing
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.
