A trajectory is a sequence of locations, each associated with a timestamp, describing the movement of a point. Trajectory data is becoming increasingly available and the size of recorded trajectories is getting larger. In this paper we study the problem of compressing planar trajectories such that the most common spatio-temporal queries can still be answered approximately after the compression has taken place. In the process, we develop an implementation of the Douglas-Peucker path-simplification algorithm which works efficiently even in the case where the polygonal path given as input is allowed to self-intersect. For a polygonal path of size n, the processing time is O(n log^k n) for k = 2 or k = 3 depending on the type of simplification.

@article{GKMOW2009J,
  author = {Joachim Gudmundsson and Jyrki Katajainen and Damian Merrick and
    Cahya Ong and Thomas Wolle},
  title = {Compressing spatio-temporal trajectories},
  journaltitle = {Computational Geometry---Theory and Applications},
  volume = {42},
  number = {9},
  year = {2009},
  pages = {825--841},
}