{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:22:48Z","timestamp":1760170968319,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,12,8]],"date-time":"2015-12-08T00:00:00Z","timestamp":1449532800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"EU Cost Action IC0903"},{"name":"NSF","award":["CCF 08-30691 and CCF 11-17336"],"award-info":[{"award-number":["CCF 08-30691 and CCF 11-17336"]}]},{"name":"NSA MSP","award":["H98230-10-1-0210"],"award-info":[{"award-number":["H98230-10-1-0210"]}]},{"DOI":"10.13039\/501100003246","name":"Netherlands Organisation for Scientific Research","doi-asserted-by":"crossref","award":["639.021.123, 612.001.022 and 612.065.823"],"award-info":[{"award-number":["639.021.123, 612.001.022 and 612.065.823"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,2,12]]},"abstract":"<jats:p>\n            In the trajectory segmentation problem, we are given a polygonal trajectory with\n            <jats:italic>n<\/jats:italic>\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\n            <jats:italic>monotone<\/jats:italic>\n            criteria: criteria with the property that if they hold on a certain segment, they also hold on every subsegment of that segment. To the best of our knowledge, no theoretical results are known for nonmonotone criteria.\n          <\/jats:p>\n          <jats:p>\n            We present a broader study of the segmentation problem, and suggest a general framework for solving it, based on the\n            <jats:italic>start-stop diagram<\/jats:italic>\n            : a 2-dimensional diagram that represents all valid and invalid segments of a given trajectory. This yields two subproblems: (1) computing the start-stop diagram, and (2) finding the optimal segmentation for a given diagram. We show that (2) is NP-hard in general. However, we identify properties of the start-stop diagram that make the problem tractable and give a polynomial-time algorithm for this case.\n          <\/jats:p>\n          <jats:p>\n            We study two concrete nonmonotone criteria that arise in practical applications in more detail. Both are based on a given univariate attribute function\n            <jats:italic>f<\/jats:italic>\n            over the domain of the trajectory. We say a segment satisfies an\n            <jats:italic>outlier-tolerant criterion<\/jats:italic>\n            if the value of\n            <jats:italic>f<\/jats:italic>\n            lies within a certain range for at least a given percentage of the length of the segment. We say a segment satisfies a\n            <jats:italic>standard deviation criterion<\/jats:italic>\n            if the standard deviation of\n            <jats:italic>f<\/jats:italic>\n            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\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>kn<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) time and on the standard deviation criterion in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>kn<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) time, where\n            <jats:italic>n<\/jats:italic>\n            is the number of vertices of the input trajectory and\n            <jats:italic>k<\/jats:italic>\n            is the number of segments in an optimal solution.\n          <\/jats:p>","DOI":"10.1145\/2660772","type":"journal-article","created":{"date-parts":[[2015,12,10]],"date-time":"2015-12-10T14:22:10Z","timestamp":1449757330000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Segmentation of Trajectories on Nonmonotone Criteria"],"prefix":"10.1145","volume":"12","author":[{"given":"Boris","family":"Aronov","sequence":"first","affiliation":[{"name":"Polytechnic Institute of NYU"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anne","family":"Driemel","sequence":"additional","affiliation":[{"name":"TU Eindhoven, MB Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc Van","family":"Kreveld","sequence":"additional","affiliation":[{"name":"Utrecht University, TB Utrecht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maarten","family":"L\u00f6ffler","sequence":"additional","affiliation":[{"name":"Utrecht University, TB Utrecht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Staals","sequence":"additional","affiliation":[{"name":"Utrecht University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,12,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000064"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150411"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-5193(88)80038-9"},{"key":"e_1_2_1_4_1","first-page":"33","article-title":"Segmenting trajectories: A framework and algorithms using spatiotemporal criteria","volume":"3","author":"Buchin M.","year":"2011","unstructured":"M. Buchin , A. Driemel , M. J. van Kreveld , and V. Sacristan . 2011 . Segmenting trajectories: A framework and algorithms using spatiotemporal criteria . Journal of Spatial Information Science 3 , 1 (2011), 33 -- 63 . M. Buchin, A. Driemel, M. J. van Kreveld, and V. Sacristan. 2011. Segmenting trajectories: A framework and algorithms using spatiotemporal criteria. Journal of Spatial Information Science 3, 1 (2011), 33--63.","journal-title":"Journal of Spatial Information Science"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ecoinf.2008.10.002"},{"volume-title":"Proc. Algorithms and Computation (LNCS 650)","author":"Chan W. S.","key":"e_1_2_1_6_1","unstructured":"W. S. Chan and F. Chin . 1992. Approximation of polygonal curves with minimum number of line segments . In Proc. Algorithms and Computation (LNCS 650) . 378--387. W. S. Chan and F. Chin. 1992. Approximation of polygonal curves with minimum number of line segments. In Proc. Algorithms and Computation (LNCS 650). 378--387."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"P. Chundi and D. J. Rosenkrantz. 2009. Segmentation of time series data. In Encyclopedia of Data Warehousing and Mining John Wang (Ed.). IGI Global 1753--1758.  P. Chundi and D. J. Rosenkrantz. 2009. Segmentation of time series data. In Encyclopedia of Data Warehousing and Mining John Wang (Ed.). IGI Global 1753--1758.","DOI":"10.4018\/978-1-60566-010-3.ch267"},{"key":"e_1_2_1_8_1","unstructured":"S. Dasgupta C. Papadimitriou and U. Vazirani. 2008. Algorithms. McGraw-Hill.   S. Dasgupta C. Papadimitriou and U. Vazirani. 2008. Algorithms. McGraw-Hill."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03427-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2009.07.008"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.3138\/FM57-6770-U75U-7727"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(81)90028-5"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195993000257"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1461-0248.2009.01293.x"},{"key":"e_1_2_1_15_1","volume-title":"Computational Morphology: A Computational Geometric Approach to the Analysis of Form","author":"Imai H.","year":"1988","unstructured":"H. Imai and M. Iri . 1988 . Polygonal approximation of curve-formulations and algorithms. Computational Morphology: A Computational Geometric Approach to the Analysis of Form (1988), 71--86. H. Imai and M. Iri. 1988. Polygonal approximation of curve-formulations and algorithms. Computational Morphology: A Computational Geometric Approach to the Analysis of Form (1988), 71--86."},{"volume-title":"Proc. 18th International Conference on Geoinformatics. IEEE, 1--5.","author":"Li X.","key":"e_1_2_1_16_1","unstructured":"X. Li , X. Li , D. Tang , and X. Xu . 2010. Deriving features of traffic flow around an intersection from trajectories of vehicles . In Proc. 18th International Conference on Geoinformatics. IEEE, 1--5. X. Li, X. Li, D. Tang, and X. Xu. 2010. Deriving features of traffic flow around an intersection from trajectories of vehicles. In Proc. 18th International Conference on Geoinformatics. IEEE, 1--5."},{"key":"e_1_2_1_17_1","volume-title":"Proc. 16th International Conference on Pattern Recognition (ICPR\u201902)","volume":"1","author":"Mann R.","unstructured":"R. Mann , A. D. Jepson , and T. El-Maraghi . 2002. Trajectory segmentation using dynamic programming . In Proc. 16th International Conference on Pattern Recognition (ICPR\u201902) , Vol. 1 . 331--334. R. Mann, A. D. Jepson, and T. El-Maraghi. 2002. Trajectory segmentation using dynamic programming. In Proc. 16th International Conference on Pattern Recognition (ICPR\u201902), Vol. 1. 331--334."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0800375105"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0146-664X(72)80017-0"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1352-2310(97)00457-3"},{"volume-title":"Proc. 6th SIAM International Conference on Data Mining. 314--325","author":"Terzi E.","key":"e_1_2_1_21_1","unstructured":"E. Terzi and P. Tsaparas . 2006. Efficient algorithms for sequence segmentation . In Proc. 6th SIAM International Conference on Data Mining. 314--325 . E. Terzi and P. Tsaparas. 2006. Efficient algorithms for sequence segmentation. In Proc. 6th SIAM International Conference on Data Mining. 314--325."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.2193\/2009-155"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2093973.2093981"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2660772","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2660772","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:56:13Z","timestamp":1750229773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2660772"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,8]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2,12]]}},"alternative-id":["10.1145\/2660772"],"URL":"https:\/\/doi.org\/10.1145\/2660772","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2015,12,8]]},"assertion":[{"value":"2013-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}