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
Gudmundsson, J, Huang, Z, van Renssen, A
& Wong, S 2023,
Computing a Subtrajectory Cluster from c-Packed Trajectories. in S Iwata, S Iwata & N Kakimura (eds),
34th International Symposium on Algorithms and Computation, ISAAC 2023., 34, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 283, 34th International Symposium on Algorithms and Computation, ISAAC 2023, Kyoto, Japan,
03/12/2023.
https://doi.org/10.4230/LIPIcs.ISAAC.2023.34APA
Gudmundsson, J., Huang, Z., van Renssen, A.
, & Wong, S. (2023).
Computing a Subtrajectory Cluster from c-Packed Trajectories. In S. Iwata, S. Iwata, & N. Kakimura (Eds.),
34th International Symposium on Algorithms and Computation, ISAAC 2023 [34] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 283
https://doi.org/10.4230/LIPIcs.ISAAC.2023.34Vancouver
Gudmundsson J, Huang Z, van Renssen A
, Wong S.
Computing a Subtrajectory Cluster from c-Packed Trajectories. In Iwata S, Iwata S, Kakimura N, editors, 34th International Symposium on Algorithms and Computation, ISAAC 2023. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2023. 34. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 283).
https://doi.org/10.4230/LIPIcs.ISAAC.2023.34Author
Gudmundsson, Joachim ; Huang, Zijin ; van Renssen, André ; Wong, Sampson. / Computing a Subtrajectory Cluster from c-Packed Trajectories. 34th International Symposium on Algorithms and Computation, ISAAC 2023. editor / Satoru Iwata ; Satoru Iwata ; Naonori Kakimura. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 283).
Bibtex
@inproceedings{0b25555672ef4a8ba366610291c4eddf,
title = "Computing a Subtrajectory Cluster from c-Packed Trajectories",
abstract = "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{\'e}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.",
keywords = "c-packed trajectories, Computational geometry, Subtrajectory cluster",
author = "Joachim Gudmundsson and Zijin Huang and {van Renssen}, Andr{\'e} and Sampson Wong",
note = "Publisher Copyright: {\textcopyright} Joachim Gudmundsson, Zijin Huang, Andr{\'e} van Renssen, and Sampson Wong; licensed under Creative Commons License CC-BY 4.0.; 34th International Symposium on Algorithms and Computation, ISAAC 2023 ; Conference date: 03-12-2023 Through 06-12-2023",
year = "2023",
doi = "10.4230/LIPIcs.ISAAC.2023.34",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Satoru Iwata and Satoru Iwata and Naonori Kakimura",
booktitle = "34th International Symposium on Algorithms and Computation, ISAAC 2023",
}
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 -
