Computing a Subtrajectory Cluster from c-Packed Trajectories
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Computing a Subtrajectory Cluster from c-Packed Trajectories. / Gudmundsson, Joachim; Huang, Zijin; van Renssen, André; Wong, Sampson.
34th International Symposium on Algorithms and Computation, ISAAC 2023. ed. / Satoru Iwata; Satoru Iwata; Naonori Kakimura. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. 34 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 283).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Computing a Subtrajectory Cluster from c-Packed Trajectories
AU - Gudmundsson, Joachim
AU - Huang, Zijin
AU - van Renssen, André
AU - Wong, Sampson
N1 - Publisher Copyright: © Joachim Gudmundsson, Zijin Huang, André van Renssen, and Sampson Wong; licensed under Creative Commons License CC-BY 4.0.
PY - 2023
Y1 - 2023
N2 - We present a near-linear time approximation algorithm for the subtrajectory cluster problem of c-packed trajectories. Given a trajectory T of complexity n, an approximation factor ε, and a desired distance d, the problem involves finding m subtrajectories of T such that their pair-wise Fréchet distance is at most (1 + ε)d. 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 [24] established an Ω(n3) lower bound unless the Strong Exponential Time Hypothesis fails, and they presented an O(n3 log2 n) time algorithm. We circumvent this conditional lower bound by studying subtrajectory cluster on c-packed trajectories, resulting in an algorithm with an O((c2n/ε2) log(c/ε) log(n/ε)) time complexity.
AB - We present a near-linear time approximation algorithm for the subtrajectory cluster problem of c-packed trajectories. Given a trajectory T of complexity n, an approximation factor ε, and a desired distance d, the problem involves finding m subtrajectories of T such that their pair-wise Fréchet distance is at most (1 + ε)d. 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 [24] established an Ω(n3) lower bound unless the Strong Exponential Time Hypothesis fails, and they presented an O(n3 log2 n) time algorithm. We circumvent this conditional lower bound by studying subtrajectory cluster on c-packed trajectories, resulting in an algorithm with an O((c2n/ε2) log(c/ε) log(n/ε)) time complexity.
KW - c-packed trajectories
KW - Computational geometry
KW - Subtrajectory cluster
U2 - 10.4230/LIPIcs.ISAAC.2023.34
DO - 10.4230/LIPIcs.ISAAC.2023.34
M3 - Article in proceedings
AN - SCOPUS:85179124591
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 34th International Symposium on Algorithms and Computation, ISAAC 2023
A2 - Iwata, Satoru
A2 - Iwata, Satoru
A2 - Kakimura, Naonori
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 34th International Symposium on Algorithms and Computation, ISAAC 2023
Y2 - 3 December 2023 through 6 December 2023
ER -
ID: 390893259