{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:27:02Z","timestamp":1787333222613,"version":"build-2736575974"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>An algorithm that constructs a continuous piecewise linear representation, subject to a certain slope\/segment length constraint, of a given set of data is described. The algorithm yields an optimal or near optimal representation, subject to this constraint, in the $L_{\\infty}$ norm and does so in at worst $O(nK)$ time, where n is the number of data points and K the number of segments. The constraint is determined by a user-specified parameter, $t_{\\min}$, which dictates a lower bound for the distance between opposite-sign slope discontinuities. For reasonable $t_{\\min}$ values, the resulting representation of the data captures the signal and both smooths the noise and provides a measure of it. This representation is useful for applications that require a specified interval for the data values and also allows easy and continuous interpolation of ranges between recorded time points. The algorithm is described, some of its properties are proven, and its capabilities demonstrated with several examples. Comparisons are made with alternative techniques.<\/jats:p>","DOI":"10.1137\/090769077","type":"journal-article","created":{"date-parts":[[2010,8,24]],"date-time":"2010-08-24T18:11:23Z","timestamp":1282673483000},"page":"2584-2602","source":"Crossref","is-referenced-by-count":6,"title":["A Linear Time Algorithm for Near Minimax Continuous Piecewise Linear Representations of Discrete Data"],"prefix":"10.1137","volume":"32","author":[{"given":"Emily K.","family":"Szusz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Allan R.","family":"Willms","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,8,24]]},"reference":[{"key":"R1","unstructured":"K. E. Atkinson,\n                      An Introduction to Numerical Analysis\n                      , 2nd ed., John Wiley & Sons, New York, 1989."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/366573.366611"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/1206040.1206046"},{"key":"R4","first-page":"121","volume":"10","author":"Douglas D. H.","year":"1973","journal-title":"Canad. Cartographer"},{"key":"R5","unstructured":"W. Fitzgerald, D. Lemire, and M. Brooks,\n                      Quasi-monotonic segmentation of state variable behavior for reactive control\n                      , in Proceedings of the National Conference on Artificial Intelligence, Vol. 20, Part 3, 2005, pp. 1145\u20131150."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/321281.321282"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/368637.368753"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/S0005-1098(01)00284-9"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"E. Keogh, S. Chu, D. Hart, and M. Pazzani,\n                      An online algorithm for segmenting time series\n                      , in Proceedings of the IEEE International Conference on Data Mining, San Jose, CA, 2001, pp. 289\u2013296.","DOI":"10.1109\/ICDM.2001.989531"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1080\/00207160701694153"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1021\/ie0707725"},{"key":"R12","unstructured":"T. Palpanas, M. Vlachos, E. J. Keogh, D. Gunopulos, and W. Truppel,\n                      Online amnesic approximation of streaming time series\n                      , in ICDE, IEEE Computer Society, Washington, DC, 2004, pp. 338\u2013349."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1973.5009136"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1974.224041"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9045(74)90058-6"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0895-7177(92)90048-P"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/11.2.211"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0378-4754(90)90005-4"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/S0146-664X(72)80017-0"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"P. J. Schneider,\n                      An algorithm for automatically fitting digitized curves\n                      , in Graphics Gems, A. Glassner, ed., Academic Press, Boston, MA, 1990, pp. 612\u2013626.","DOI":"10.1016\/B978-0-08-050753-8.50132-7"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"H. Shatkay and S. B. Zdonik,\n                      Approximate queries and representations for large data sequences\n                      , in Proceedings of the 12th IEEE International Conference on Data Engineering, 1996, pp. 536\u2013545.","DOI":"10.1109\/ICDE.1996.492204"},{"key":"R22","unstructured":"E. L. Stiefel,\n                      Numerical methods of Tchebycheff approximation\n                      , in On Numerical Approximation, R. E. Langer, ed., University of Wisconsin Press, Madison, WI, 1959, pp. 217\u2013232."},{"key":"R23","first-page":"1","volume":"32","author":"Stout Q. F.","year":"2000","journal-title":"Comput. Sci. Statist."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/j.mbs.2006.11.009"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1007\/s11155-006-9009-2"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2005.07.039"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2006.03.018"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/080732316"},{"key":"R29","unstructured":"D. G. Wilson,\n                      Piecewise linear approximations of fewest line segments\n                      , in AFIPS Conference Proceedings Vol. 40, the 1972 Spring Joint Computer Conference, Montvale, NJ, 1972, pp. 187\u2013198."}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090769077","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:42:27Z","timestamp":1787330547000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090769077"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090769077"],"URL":"https:\/\/doi.org\/10.1137\/090769077","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}