Computing a Subtrajectory Cluster from c-packed Trajectories

2023/07/20 by Gudmundsson, Joachim, Huang, Zijin, van Renssen, André +1 · 2 citations
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2307.10610

Abstract

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 \citeGudmundssonWong2022Cubicupperlower established an Ω(n³) lower bound unless the Strong Exponential Time Hypothesis fails, and they presented an O(n³ log² 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² n/ε²)log(c/ε)log(n/ε)) time complexity.

Cited by

• Computing the Fréchet Distance When Just One Curve is c-Packed: A Simple Almost-Tight Algorithm
• A WSPD, Separator and Small Tree Cover for c-packed Graphs

Related

• Cubic upper and lower bounds for subtrajectory clustering under the continuous Fréchet distance
• Faster, Deterministic and Space Efficient Subtrajectory Clustering
• Efficient Greedy Discrete Subtrajectory Clustering
• Subtrajectory Clustering and Coverage Maximization in Cubic Time, or Better
• Subtrajectory Clustering: Finding Set Covers for Set Systems of Subcurves