Compressing spatio-temporal trajectories

被引：30

作者：

Gudmundsson, Joachim ^{[1
]}

Katajainen, Jyrki ^{[2
]}

Merrick, Damian ^{[1
,3
]}

Ong, Cahya ^{[4
]}

Wolle, Thomas ^{[1
]}

机构：

[1] NICTA Sydney, Alexandria, NSW 1435, Australia

[2] Univ Copenhagen, Dept Comp, DK-2100 Copenhagen E, Denmark

[3] Univ Sydney, Sch Informat Technol, Sydney, NSW 2006, Australia

[4] Univ New S Wales, Sch Comp Sci & Engn, Sydney, NSW 2052, Australia

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2009年 / 42卷 / 09期

关键词：

Trajectory compression; Polygonal-chain approximation; Path simplification; Spatio-temporal queries; Half-plane furthest-point queries; Convex hulls; ALGORITHM;

D O I：

10.1016/j.comgeo.2009.02.002

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. Crown Copyright (C) 2009 Published by Elsevier B.V. All rights reserved.

引用

页码：825 / 841

页数：17

共 21 条

[1] Efficient algorithms for approximating polygonal chains [J].