{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,6]],"date-time":"2023-01-06T07:50:08Z","timestamp":1672991408252},"reference-count":10,"publisher":"World Scientific Pub Co Pte Lt","issue":"02n03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2006,6]]},"abstract":"<jats:p> We study the problem of maintaining a (1 + \u220a)-factor approximation of the diameter of a stream of points under the sliding window model. In one dimension, we give a simple algorithm that only needs to store [Formula: see text] points at any time, where the parameter R denotes the \"spread\" of the point set. This bound is optimal and improves Feigenbaum, Kannan, and Zhang's recent solution by two logarithmic factors. We then extend our one-dimensional algorithm to higher constant dimensions and, at the same time, correct an error in the previous solution. In high nonconstant dimensions, we also observe a constant-factor approximation algorithm that requires sublinear space. Related optimization problems, such as the width, are also considered in the two-dimensional case. <\/jats:p>","DOI":"10.1142\/s0218195906001975","type":"journal-article","created":{"date-parts":[[2006,4,27]],"date-time":"2006-04-27T08:53:13Z","timestamp":1146127993000},"page":"145-157","source":"Crossref","is-referenced-by-count":6,"title":["GEOMETRIC OPTIMIZATION PROBLEMS OVER SLIDING WINDOWS"],"prefix":"10.1142","volume":"16","author":[{"given":"TIMOTHY M.","family":"CHAN","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Waterloo, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BASHIR S.","family":"SADJAD","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Waterloo, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008736"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(92)90001-9"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02712871"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1127"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195902000748"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1105-2"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-001-0029-8"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195906001975","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:20:29Z","timestamp":1565176829000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195906001975"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6]]},"references-count":10,"journal-issue":{"issue":"02n03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2006,6]]}},"alternative-id":["10.1142\/S0218195906001975"],"URL":"https:\/\/doi.org\/10.1142\/s0218195906001975","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6]]}}}