Computing a Subtrajectory Cluster from c-Packed Trajectories
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Fulltext
Final published version, 807 KB, PDF document
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.
Original language | English |
---|---|
Title of host publication | 34th International Symposium on Algorithms and Computation, ISAAC 2023 |
Editors | Satoru Iwata, Satoru Iwata, Naonori Kakimura |
Number of pages | 15 |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publication date | 2023 |
Article number | 34 |
ISBN (Electronic) | 9783959772891 |
DOIs | |
Publication status | Published - 2023 |
Event | 34th International Symposium on Algorithms and Computation, ISAAC 2023 - Kyoto, Japan Duration: 3 Dec 2023 → 6 Dec 2023 |
Conference
Conference | 34th International Symposium on Algorithms and Computation, ISAAC 2023 |
---|---|
Land | Japan |
By | Kyoto |
Periode | 03/12/2023 → 06/12/2023 |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 283 |
ISSN | 1868-8969 |
Bibliographical note
Publisher Copyright:
© Joachim Gudmundsson, Zijin Huang, André van Renssen, and Sampson Wong; licensed under Creative Commons License CC-BY 4.0.
- c-packed trajectories, Computational geometry, Subtrajectory cluster
Research areas
ID: 390893259