{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,9]],"date-time":"2025-02-09T04:10:21Z","timestamp":1739074221997,"version":"3.37.0"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,4,23]],"date-time":"2009-04-23T00:00:00Z","timestamp":1240444800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2009,10]]},"DOI":"10.1007\/s00454-009-9165-3","type":"journal-article","created":{"date-parts":[[2009,4,22]],"date-time":"2009-04-22T17:56:18Z","timestamp":1240422978000},"page":"469-488","source":"Crossref","is-referenced-by-count":9,"title":["Dynamic Coresets"],"prefix":"10.1007","volume":"42","author":[{"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,4,23]]},"reference":[{"key":"9165_CR1","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/PL00009427","volume":"21","author":"P.K. Agarwal","year":"1999","unstructured":"Agarwal, P.K., Aronov, B., Sharir, M.: Line transversals of balls and smallest enclosing cylinders in three dimensions. Discrete Comput. Geom. 21, 373\u2013388 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"9165_CR2","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1145\/1008731.1008736","volume":"51","author":"P.K. Agarwal","year":"2004","unstructured":"Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Approximating extent measures of points. J. ACM 51, 606\u2013635 (2004)","journal-title":"J. ACM"},{"key":"9165_CR3","first-page":"1","volume-title":"Current Trends in Combinatorial and Computational Geometry","author":"P.K. Agarwal","year":"2007","unstructured":"Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Geometric approximation via coresets. In: Goodman, J.E., Pach, J., Welzl, E. (eds.) Current Trends in Combinatorial and Computational Geometry, pp.\u00a01\u201330. Cambridge University Press, New York (2007)"},{"key":"9165_CR4","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/s00454-007-9013-2","volume":"29","author":"P.K. Agarwal","year":"2008","unstructured":"Agarwal, P.K., Har-Peled, S., Yu, H.: Robust shape fitting via peeling and grating coresets. Discrete Comput. Geom. 29, 38\u201358 (2008)","journal-title":"Discrete Comput. Geom."},{"key":"9165_CR5","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF01293483","volume":"13","author":"P.K. Agarwal","year":"1995","unstructured":"Agarwal, P.K., Matou\u0161ek, J.: Dynamic half-space range reporting and its applications. Algorithmica 13, 325\u2013345 (1995)","journal-title":"Algorithmica"},{"key":"9165_CR6","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/S0196-6774(02)00295-X","volume":"46","author":"P.K. Agarwal","year":"2003","unstructured":"Agarwal, P.K., Procopiuc, C.M.: Approximation algorithms for projective clustering. J. Algorithms 46, 115\u2013139 (2003)","journal-title":"J. Algorithms"},{"key":"9165_CR7","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0925-7721(91)90001-U","volume":"1","author":"P.K. Agarwal","year":"1991","unstructured":"Agarwal, P.K., Sharir, M.: Off-line dynamic maintenance of the width of a planar point set. Comput. Geom. Theory Appl. 1, 65\u201378 (1991)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9165_CR8","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/BF02712871","volume":"16","author":"P.K. Agarwal","year":"1996","unstructured":"Agarwal, P.K., Sharir, M.: Efficient randomized algorithms for some geometric optimization problems. Discrete Comput. Geom. 16, 317\u2013337 (1996)","journal-title":"Discrete Comput. Geom."},{"key":"9165_CR9","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Yu, H.: A space-optimal data-stream algorithm for coresets in the plane. In: Proc. 23rd ACM Sympos. Comput. Geom., pp. 1\u201310 (2007)","DOI":"10.1145\/1247069.1247071"},{"key":"9165_CR10","unstructured":"B\u0103doiu, M., Clarkson, K.L.: Optimal core-sets for balls. In: Proc. 14th ACM-SIAM Sympos. Discrete Algorithms, pp. 801\u2013802 (2003)"},{"key":"9165_CR11","doi-asserted-by":"crossref","unstructured":"B\u0103doiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: Proc. 34th ACM Sympos. Theory Comput., pp. 250\u2013257 (2002)","DOI":"10.1145\/509907.509947"},{"key":"9165_CR12","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1006\/jagm.2000.1127","volume":"38","author":"G. Barequet","year":"2001","unstructured":"Barequet, G., Har-Peled, S.: Efficiently approximating the minimum-volume bounding box of a point set in three dimensions. J. Algorithms 38, 91\u2013109 (2001)","journal-title":"J. Algorithms"},{"key":"9165_CR13","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"J. Bentley","year":"1980","unstructured":"Bentley, J., Saxe, J.: Decomposable searching problems I: static-to-dynamic transformation. J. Algorithms 1, 301\u2013358 (1980)","journal-title":"J. Algorithms"},{"key":"9165_CR14","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Jacob, R.: Dynamic planar convex hull. In: Proc. 43rd IEEE Sympos. Found. Comput. Sci., pp. 617\u2013626 (2002)","DOI":"10.1109\/SFCS.2002.1181985"},{"key":"9165_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/363647.363652","volume":"48","author":"T.M. Chan","year":"2001","unstructured":"Chan, T.M.: Dynamic planar convex hull operations in near-logarithmic amortized time. J. ACM, 48, 1\u201312 (2001)","journal-title":"J. ACM"},{"key":"9165_CR16","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1142\/S0218195902000748","volume":"12","author":"T.M. Chan","year":"2002","unstructured":"Chan, T.M.: Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus. Int. J. Comput. Geom. Appl. 12, 67\u201385 (2002)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9165_CR17","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/s00454-003-2923-8","volume":"30","author":"T.M. Chan","year":"2003","unstructured":"Chan, T.M.: A fully dynamic algorithm for planar width. Discrete Comput. Geom. 30, 17\u201324 (2003)","journal-title":"Discrete Comput. Geom."},{"key":"9165_CR18","doi-asserted-by":"crossref","first-page":"700","DOI":"10.1137\/S0097539702404389","volume":"32","author":"T.M. Chan","year":"2003","unstructured":"Chan, T.M.: Semi-online maintenance of geometric optima and measures. SIAM J. Comput. 32, 700\u2013716 (2003)","journal-title":"SIAM J. Comput."},{"key":"9165_CR19","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. In: Proc. 17th ACM-SIAM Sympos. Discrete Algorithms, pp. 1196\u20131202 (2006)","DOI":"10.1145\/1109557.1109689"},{"key":"9165_CR20","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/j.comgeo.2005.10.002","volume":"35","author":"T.M. Chan","year":"2006","unstructured":"Chan, T.M.: Faster core-set constructions and data stream algorithms in fixed dimensions. Comput. Geom. Theory Appl. 35, 20\u201335 (2006)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9165_CR21","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/j.ipl.2008.02.008","volume":"107","author":"T.M. Chan","year":"2008","unstructured":"Chan, T.M.: Well-separated pair decomposition in linear time? Inf. Process. Lett. 107, 138\u2013141 (2008)","journal-title":"Inf. Process. Lett."},{"key":"9165_CR22","unstructured":"Chan, T.M., P\u01cetra\u015fcu, M.: Transdichotomous results in computational geometry, I: Point location in sublogarithmic time. SIAM J. Comput. (to appear). Preliminary versions in Proc. 47th IEEE Sympos. Found. Comput. Sci., pp. 325\u2013332, 333\u2013342 (2006)"},{"key":"9165_CR23","unstructured":"Chan, T.M., P\u01cetra\u015fcu, M.: Transdichotomous results in computational geometry, II: Offline search. In: Proc. 39th ACM Sympos. Theory Comput., pp. 31\u201339 (2007)"},{"key":"9165_CR24","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1142\/S0218195906001975","volume":"16","author":"T.M. Chan","year":"2006","unstructured":"Chan, T.M., Sadjad, B.S.: Geometric optimization problems over sliding windows. Int. J. Comput. Geom. Appl. 16, 145\u2013157 (2006)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9165_CR25","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1109\/TIT.1985.1057060","volume":"IT-31","author":"B. Chazelle","year":"1985","unstructured":"Chazelle, B.: On the convex layers of a planar set. IEEE Trans. Inf. Theory IT-31, 509\u2013517 (1985)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9165_CR26","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1142\/S021819599600023X","volume":"6","author":"K.L. Clarkson","year":"1996","unstructured":"Clarkson, K.L., Eppstein, D., Miller, G.L., Sturtivant, C., Teng, S.-H.: Approximating center points with iterative Radon points. Int. J. Comput. Geom. Appl. 6, 357\u2013377 (1996)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9165_CR27","unstructured":"Duncan, C.A., Goodrich, M.T., Ramos, E.A.: Efficient approximation and optimization algorithms for computational metrology. In: Proc. 8th ACM-SIAM Sympos. Discrete Algorithms, pp. 121\u2013130 (1997)"},{"key":"9165_CR28","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/11590156_8","volume-title":"Proc. 25th Int. Conf. Found. Soft. Tech. Theoret. Comput. Sci.","author":"M. Edwards","year":"2005","unstructured":"Edwards, M., Varadarajan, K.R.: No coreset, no cry: II. In: Proc. 25th Int. Conf. Found. Soft. Tech. Theoret. Comput. Sci. Lect. Notes Comput. Sci., vol.\u00a03821. Springer, Berlin, pp.\u00a0107\u2013115 (2005)"},{"key":"9165_CR29","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/s00453-004-1105-2","volume":"41","author":"J. Feigenbaum","year":"2004","unstructured":"Feigenbaum, J., Kannan, S., Zhang, J.: Computing diameter in the streaming and sliding-window models. Algorithmica 41, 25\u201341 (2004)","journal-title":"Algorithmica"},{"key":"9165_CR30","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1142\/S0218195908002520","volume":"18","author":"G. Frahling","year":"2008","unstructured":"Frahling, G., Indyk, P., Sohler, C.: Sampling in dynamic data streams and applications. Int. J. Comput. Geom. Appl. 18, 3\u201328 (2008)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9165_CR31","doi-asserted-by":"crossref","unstructured":"Frahling, G., Sohler, C.: Coresets in dynamic geometric data streams. In: Proc. 37th ACM Sympos. Theory Comput., pp. 209\u2013217 (2005)","DOI":"10.1145\/1060590.1060622"},{"key":"9165_CR32","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"T. Gonzalez","year":"1985","unstructured":"Gonzalez, T.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"9165_CR33","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/s00454-004-2822-7","volume":"31","author":"S. Har-Peled","year":"2004","unstructured":"Har-Peled, S.: Clustering motion. Discrete Comput. Geom. 31, 545\u2013565 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"9165_CR34","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1007\/978-3-540-30538-5_27","volume-title":"Proc. 24th Int. Conf. Found. Soft. Tech. Theoret. Comput. Sci.","author":"S. Har-Peled","year":"2004","unstructured":"Har-Peled, S.: No coreset, no cry. In: Proc. 24th Int. Conf. Found. Soft. Tech. Theoret. Comput. Sci. Lect. Notes Comput. Sci., vol.\u00a03328. Springer, Berlin, pp.\u00a0324\u2013335 (2004)"},{"key":"9165_CR35","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00454-006-1271-x","volume":"37","author":"S. Har-Peled","year":"2007","unstructured":"Har-Peled, S., Kushal, A.: Smaller coresets for k-median and k-means clustering. Discrete Comput. Geom. 37, 3\u201319 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"9165_CR36","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mazumdar, S.: Coresets for k-means and k-median clustering and their applications. In: Proc. 36th ACM Sympos. Theory. Comput., pp. 291\u2013300 (2004)","DOI":"10.1145\/1007352.1007400"},{"key":"9165_CR37","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Varadarajan, K.R.: Projective clustering in high dimensions using core-sets. In: Proc. 18th ACM Sympos. Comput. Geom., pp. 312\u2013318 (2002)","DOI":"10.1145\/513400.513440"},{"key":"9165_CR38","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1137\/S0097539703427963","volume":"33","author":"S. Har-Peled","year":"2004","unstructured":"Har-Peled, S., Wang, Y.: Shape fitting with outliers. SIAM J. Comput. 33, 269\u2013285 (2004)","journal-title":"SIAM J. Comput."},{"key":"9165_CR39","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Algorithms for dynamic geometric problems over data streams. In: Proc. 36th ACM Sympos. Theory Comput., pp. 373\u2013380 (2004)","DOI":"10.1145\/1007352.1007413"},{"key":"9165_CR40","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1142\/S021819599300021X","volume":"3","author":"R. Janardan","year":"1993","unstructured":"Janardan, R.: On maintaining the width and diameter of a planar point-set online. Int. J. Comput. Geom. Appl. 3, 331\u2013344 (1993)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9165_CR41","unstructured":"Matias, Y., Vitter, J.S., Young, N.E.: Approximate data structures with applications. In: Proc 5th ACM-SIAM Sympos. Discrete Algorithm, pp. 187\u2013194 (1994)"},{"key":"9165_CR42","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1016\/B978-044482537-7\/50014-0","volume-title":"Handbook of Computational Geometry","author":"J. Matou\u0161ek","year":"2000","unstructured":"Matou\u0161ek, J.: Derandomization in computational geometry. In: Urrutia, J., Sack, J. (eds.) Handbook of Computational Geometry. North-Holland, Amsterdam, pp.\u00a0559\u2013595 (2000)"},{"key":"9165_CR43","unstructured":"Overmars, M.H.: The Design of Dynamic Data Structures. Lect. Notes in Comput. Sci., vol.\u00a0156. Springer, Berlin (1983)"},{"key":"9165_CR44","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M.H. Overmars","year":"1981","unstructured":"Overmars, M.H., van Leeuwen, J.: Maintenance of configurations in the plane. J. Comput. Sys. Sci. 23, 166\u2013204 (1981)","journal-title":"J. Comput. Sys. Sci."},{"key":"9165_CR45","doi-asserted-by":"crossref","DOI":"10.1002\/9781118033203","volume-title":"Combinatorial Geometry","author":"J. Pach","year":"1995","unstructured":"Pach, J., Agarwal, P.K.: Combinatorial Geometry. Wiley-Interscience, New York (1995)"},{"key":"9165_CR46","unstructured":"Rote, G., Schwarz, C., Snoeyink, J.: Maintaining the approximate width of a set of points in the plane, In: Proc. 5th Canad. Conf. Comput. Geom., pp. 258\u2013263 (1993)"},{"key":"9165_CR47","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1145\/1314690.1314692","volume":"54","author":"M. Thorup","year":"2007","unstructured":"Thorup, M.: Equivalence between priority queues and sorting. J. ACM 54, 6 (2007)","journal-title":"J. ACM"},{"key":"9165_CR48","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett. 6, 80\u201382 (1977)","journal-title":"Inf. Process. Lett."},{"key":"9165_CR49","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/s00453-007-9067-9","volume":"52","author":"H. Yu","year":"2008","unstructured":"Yu, H., Agarwal, P.K., Poreddy, R., Varadarajan, K.R.: Practical methods for shape fitting and kinetic data structures using core sets. Algorithmica 52, 378\u2013402 (2008)","journal-title":"Algorithmica"},{"key":"9165_CR50","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1007\/978-3-540-87744-8_68","volume-title":"Proc. 16th European Sympos. Algorithms","author":"H. Zarrabi-Zadeh","year":"2008","unstructured":"Zarrabi-Zadeh, H.: An almost space-optimal streaming algorithm for coresets in fixed dimensions. In: Proc. 16th European Sympos. Algorithms. Lect. Notes in Comput. Sci., vol.\u00a05193. Springer, Berlin, pp.\u00a0817\u2013829 (2008)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9165-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-009-9165-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9165-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,9]],"date-time":"2025-02-09T03:56:18Z","timestamp":1739073378000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-009-9165-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,23]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["9165"],"URL":"https:\/\/doi.org\/10.1007\/s00454-009-9165-3","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2009,4,23]]}}}