We study subtrajectory clustering under the Fr\'echet distance. Given one or more trajectories, the task is to split the trajectories into several parts, such that the parts have a good clustering structure. We approach this problem via a new set cover formulation, which we think provides a natural formalization of the problem as it is studied in many applications. Given a polygonal curve $P$ with $n$ vertices in fixed dimension, integers $k$, $\ell \geq 1$, and a real value $\Delta > 0$, the goal is to find $k$ center curves of complexity at most $\ell$ such that every point on $P$ is covered by a subtrajectory that has small Fr\'echet distance to one of the $k$ center curves ($\leq \Delta$). In many application scenarios, one is interested in finding clusters of small complexity, which is controlled by the parameter $\ell$. Our main result is a bicriterial approximation algorithm: if there exists a solution for given parameters $k$, $\ell$, and $\Delta$, then our algorithm finds a set of $k'$ center curves of complexity at most $\ell$ with covering radius $\Delta'$ with $k' \in O( k \ell^2 \log (k \ell))$, and $\Delta'\leq 19 \Delta$. Moreover, within these approximation bounds, we can minimize $k$ while keeping the other parameters fixed. If $\ell$ is a constant independent of $n$, then, the approximation factor for the number of clusters $k$ is $O(\log k)$ and the approximation factor for the radius $\Delta$ is constant. In this case, the algorithm has expected running time in $ \tilde{O}\left( k m^2 + mn\right)$ and uses space in $O(n+m)$, where $m=\lceil\frac{L}{\Delta}\rceil$ and $L$ is the total arclength of the curve $P$.
翻译:我们研究的是Fr\ Pelchet 距离下的亚球群集。 如果有一条或多条轨道, 任务就是将轨迹分割成几个部分, 使各个部分具有良好的组群结构。 我们通过一个新的套装套件配方来解决这个问题, 我们认为它提供了问题自然的正规化, 正如在许多应用程序中研究的那样。 由于一个多角曲线, 美元为固定尺寸, 整数 美元, 美元= 美元= Geq美元 1美元, 实际值 $\ Delta > 0美元, 目标是找到 美元 的复杂度中心曲线 $= 美元, 这样, 美元= 美元= 美元= 美元= 美元= 美元。 在许多应用假设中, 找到这个小的复杂度, 由参数 美元= 美元= 美元 。 我们的主要结果是 美元=xxxx 的算法: 如果存在一个固定值, 美元=xxxxxxxxxx 美元的计算, 美元 美元 。