Compressing spatio-temporal trajectories (Q833705)

The authors consider the problem of simplifying trajectories and strengthen the model of \textit{H. Cao} et al. [The VLDB Journal 15, 211--228 (2006)] such that the five types of queries proposed by them can be approximated in a sound way. An algorithm very similar to the Douglas-Peucker method [\textit{D. H. Douglas, T. K. Peucker}, Algorithms for the reduction of the number of points required to represent a digitized line or its caricature, The Canadian Cartographer 10, No. 2, 112--122 (1973; doi:10.3138/FM57-6770-U75U-7727)] is proposed that produces a simplification of a path in three dimensions or a trajectory in the plane. The authors also present an \(O(n \log^2n) \)-time and an \(O(n \log^3n) \)-time implementation of the Douglas-Peucker algorithm in the plane in the case where the polygonal path can self-intersect.