TY - GEN
T1 - Segmentation of trajectories on non-monotone criteria
AU - Aronov, Boris
AU - Driemel, Anne
AU - Van Kreveld, Marc
AU - Löffler, Maarten
AU - Staals, Frank
PY - 2013
Y1 - 2013
N2 - 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(n 2 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.
AB - 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(n 2 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.
UR - http://www.scopus.com/inward/record.url?scp=84876060200&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84876060200&partnerID=8YFLogxK
U2 - 10.1137/1.9781611973105.135
DO - 10.1137/1.9781611973105.135
M3 - Conference contribution
AN - SCOPUS:84876060200
SN - 9781611972511
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1897
EP - 1911
BT - Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
PB - Association for Computing Machinery
T2 - 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Y2 - 6 January 2013 through 8 January 2013
ER -