Segmentation of Trajectories for Non-Monotone Criteria
Segmentation of Trajectories for Non-Monotone Criteria
复制标题
非单调标准的轨迹分割
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Mar van Kreveld
中科院分区：
文献类型：
--
作者：
Boris Aronov;Anne Driemel;Mar van Kreveld
在轨迹分割问题中，我们给出了一个具有n个顶点的多边形轨迹，我们必须将其细分为最少数量的不相交的段(子轨迹)，这些段(子轨迹)都满足给定的标准。众所周知，对于单调标准，这个问题是有效可解的：标准的性质是，如果它们适用于某一段，则它们也适用于该段的每一个子段[4]。就我们所知，目前还没有关于非单调准则的理论结果。
我们提出了对分割问题的更广泛的研究，并基于起止图提出了解决该问题的一般框架：表示给定轨迹的所有有效和无效段的二维图。这产生了两个子问题：(I)计算起止图，以及(Ii)为给定图找到最佳分割。我们证明了(Ii)一般是NP-难的。然而，我们确定了使问题易于处理的起止图的性质，并给出了这种情况下的多项式时间算法。
我们更详细地研究了在实际应用中出现的两个具体的非单调准则。两者都基于轨迹域上的给定单变量属性函数f。如果f的值至少在该段长度的给定百分比内处于某一范围内，则我们称该段满足离群值容忍标准。如果f在线段长度上的标准偏差低于给定的阈值，则我们称该线段满足标准偏差标准。我们证明了这两个准则都满足使分割问题易于处理的性质。特别地，我们在O(n2logn+k2)时间内基于离群点容忍准则和在O(K2)时间内基于标准偏差准则计算轨迹的最优分割，其中n是输入轨迹的顶点数，k是最优解的分段数。
In the trajectory segmentation problem we are given a polygonal trajectory with n vertices that we have to subdivide into a minimum number of disjoint segments (subtrajectories) that all satisfy a given criterion. The problem is known to be solvable efficiently for monotone criteria: criteria with the property that if they hold on a certain segment, they also hold on every subsegment of that segment [4]. To the best of our knowledge, no theoretical results are known for non-monotone criteria.
We present a broader study of the segmentation problem, and suggest a general framework for solving it, based on the start-stop diagram: a 2-dimensional diagram that represents all valid and invalid segments of a given trajectory. This yields two subproblems: (i) computing the start-stop diagram, and (ii) finding the optimal segmentation for a given diagram. We show that (ii) is NP-hard in general. However, we identify properties of the start-stop diagram that make the problem tractable, and give polynomial-time algorithm for this case.
We study two concrete non-monotone criteria that arise in practical applications in more detail. Both are based on a given univariate attribute function f over the domain of the trajectory. We say a segment satisfies an outlier-tolerant criterion if the value of f lies within a certain range for at least a given percentage of the length of the segment. We say a segment satisfies a standard deviation criterion if the standard deviation of f over the length of the segment lies below a given threshold. We show that both criteria satisfy the properties that make the segmentation problem tractable. In particular, we compute an optimal segmentation of a trajectory based on the outlier-tolerant criterion in O(n2 log n+kn2) time, and on the standard deviation criterion in O(kn2) time, where n is the number of vertices of the input trajectory and k is the number of segments in an optimal solution.