Abstract
Subtrajectory clustering is an important variant of the trajectory clustering problem, where the start and endpoints of trajectory patterns within the collected trajectory data are not known in advance. We study this problem in the form of a set cover problem for a given polygonal curve: find the smallest number k of representative curves such that any point on the input curve is contained in a subcurve that has Fréchet distance at most a given Δ to a representative curve. We focus on the case where the representative curves are line segments and approach this NPhard problem with classical techniques from the area of geometric set cover: we use a variant of the multiplicative weights update method which was first suggested by Brönniman and Goodrich for set cover instances with small VCdimension. We obtain a bicriteriaapproximation algorithm that computes a set of O(klog(k)) line segments that cover a given polygonal curve of n vertices under Fréchet distance at most O(Δ). We show that the algorithm runs in Õ(k² n + k n³) time in expectation and uses Õ(k n + n³) space. For input curves that are cpacked and lie in the plane, we bound the expected running time by Õ(k² c² n) and the space by Õ(kn + c² n). In addition, we present a variant of the algorithm that uses implicit weight updates on the candidate set and thereby achieves nearlinear running time in n without any assumptions on the input curve, while keeping the same approximation bounds. This comes at the expense of a small (polylogarithmic) dependency on the relative arclength.
BibTeX  Entry
@InProceedings{bruning_et_al:LIPIcs.ESA.2022.28,
author = {Br\"{u}ning, Frederik and Conradi, Jacobus and Driemel, Anne},
title = {{Faster Approximate Covering of Subcurves Under the Fr\'{e}chet Distance}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {28:128:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772471},
ISSN = {18688969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16966},
URN = {urn:nbn:de:0030drops169660},
doi = {10.4230/LIPIcs.ESA.2022.28},
annote = {Keywords: Clustering, Set cover, Fr\'{e}chet distance, Approximation algorithms}
}
Keywords: 

Clustering, Set cover, Fréchet distance, Approximation algorithms 
Collection: 

30th Annual European Symposium on Algorithms (ESA 2022) 
Issue Date: 

2022 
Date of publication: 

01.09.2022 