Central Trajectories

Abstract

An important task in trajectory analysis is clustering. The results of a clustering are often summarized by a single representative trajectory and an associated size of each cluster. We study the problem of computing a suitable representative of a set of similar trajectories. To this end we define a central trajectory CC, which consists of pieces of the input trajectories, switches from one entity to another only if they are within a small distance of each other, and such that at any time tt, the point C(t)C(t) is as central as possible. We measure centrality in terms of the radius of the smallest disk centered at C(t)C(t) enclosing all entities at time tt, and discuss how the techniques can be adapted to other measures of centrality. We first study the problem in R1R1, where we show that an optimal central trajectory CC representing nn trajectories, each consisting of ττ edges, has complexity Θ(τn2)Θ(τn2) and can be computed in O(τn2logn)O(τn2log⁡n) time. We then consider trajectories in RdRd with d≥2d≥2, and show that the complexity of CC is at most O(τn5/2)O(τn5/2) and can be computed in O(τn3)O(τn3) time.