Computing a Subtrajectory Cluster from c-packed Trajectories
share
We present a near-linear time approximation algorithm for the subtrajectory cluster problem of c-packed trajectories. The problem involves finding m subtrajectories within a given trajectory T such that their Fréchet distances are at most (1 + ε)d, and at least one subtrajectory must be of length l or longer. A trajectory T is c-packed if the intersection of T and any ball B with radius r is at most c · r in length. Previous results by Gudmundsson and Wong <cit.> established an Ω(n^3) lower bound unless the Strong Exponential Time Hypothesis fails, and they presented an O(n^3 log^2 n) time algorithm. We circumvent this conditional lower bound by studying subtrajectory cluster on c-packed trajectories, resulting in an algorithm with an O((c^2 n/ε^2)log(c/ε)log(n/ε)) time complexity.
READ FULL TEXT