Trajectory data is becoming increasingly available and the size of the trajectories is getting larger. In this paper we study the problem of compressing spatio-temporal trajectories such that the most common queries can still be answered approximately after the compression step has taken place. In the process we develop an O(n log^k n)-time implementation of the Douglas-Peucker algorithm in the case when the polygonal path of n vertices given as input is allowed to self-intersect.

@inproceedings{GKMOW2007C,
  author = {Joachim Gudmundsson and Jyrki Katajainen and Damian Merrick and
    Cahya Ong and Thomas Wolle},
  title = {Compressing spatio-temporal trajectories},
  booktitle = {Proceedings of the 18th International Symposium on Algorithms
    and Computation},
  series = {Lecture Notes in Computer Science},
  volume = {4835},
  publisher = {Springer-Verlag},
  year = {2007},
  pages = {763--775},
}