{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T01:58:16Z","timestamp":1780538296342,"version":"3.54.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,10,19]],"date-time":"2007-10-19T00:00:00Z","timestamp":1192752000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,11]]},"DOI":"10.1007\/s00453-007-9067-9","type":"journal-article","created":{"date-parts":[[2007,10,18]],"date-time":"2007-10-18T17:50:38Z","timestamp":1192729838000},"page":"378-402","source":"Crossref","is-referenced-by-count":15,"title":["Practical Methods for Shape Fitting and Kinetic Data Structures using Coresets"],"prefix":"10.1007","volume":"52","author":[{"given":"Hai","family":"Yu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pankaj K.","family":"Agarwal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raghunath","family":"Poreddy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kasturi R.","family":"Varadarajan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,10,19]]},"reference":[{"key":"9067_CR1","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1007\/s004540010062","volume":"24","author":"P.K. Agarwal","year":"2000","unstructured":"Agarwal, P.K., Aronov, B., Har-Peled, S., Sharir, M.: Approximation and exact algorithms for minimum-width annuli and shells. Discrete Comput. Geom. 24, 687\u2013705 (2000)","journal-title":"Discrete Comput. Geom."},{"key":"9067_CR2","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":"9067_CR3","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/s00454-001-0039-6","volume":"26","author":"P.K. Agarwal","year":"2001","unstructured":"Agarwal, P.K., Aronov, B., Sharir, M.: Exact and approximation algorithms for minimum-width cylindrical shells. Discrete Comput. Geom. 26, 307\u2013320 (2001)","journal-title":"Discrete Comput. Geom."},{"key":"9067_CR4","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/s00454-001-0019-x","volume":"26","author":"P.K. Agarwal","year":"2001","unstructured":"Agarwal, P.K., Guibas, L.J., Hershberger, J., Veach, E.: Maintaining the extent of a moving point set. Discrete Comput. Geom. 26, 353\u2013374 (2001)","journal-title":"Discrete Comput. Geom."},{"key":"9067_CR5","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":"9067_CR6","first-page":"1","volume-title":"Combinatorial and Computational Geometry","author":"P.K. Agarwal","year":"2005","unstructured":"Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Geometric approximation via coresets. In: Goodman, J.E., Pach, J., Welzl, E. (eds.) Combinatorial and Computational Geometry, pp. 1\u201330. Cambridge University Press, Cambridge (2005)"},{"key":"9067_CR7","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s00453-005-1166-x","volume":"42","author":"P.K. Agarwal","year":"2005","unstructured":"Agarwal, P.K., Procopiuc, C.M., Varadarajan, K.R.: Approximation algorithms for k-line center. Algorithmica 42, 221\u2013230 (2005)","journal-title":"Algorithmica"},{"key":"9067_CR8","doi-asserted-by":"crossref","unstructured":"Arya, S., Malamatos, T., Mount, D.: Space-efficient approximate Voronoi diagrams. In: Proc. 34th Annu. ACM Symposium on Theory Comput., pp. 721\u2013730 (2002)","DOI":"10.1145\/509907.510011"},{"key":"9067_CR9","doi-asserted-by":"crossref","first-page":"891","DOI":"10.1145\/293347.293348","volume":"45","author":"S. Arya","year":"1998","unstructured":"Arya, S., Mount, D., Netanyahu, N., Silverman, R., Wu, A.Y.: An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. J. ACM 45, 891\u2013923 (1998)","journal-title":"J. ACM"},{"key":"9067_CR10","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":"9067_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jagm.1998.0988","volume":"31","author":"J. Basch","year":"1999","unstructured":"Basch, J., Guibas, L.J., Hershberger, J.: Data structures for mobile data. J. Algorithms 31, 1\u201328 (1999)","journal-title":"J. Algorithms"},{"key":"9067_CR12","unstructured":"B\u0103doiu, M., Clarkson, K.: Smaller core-sets for balls. In: Proc. 14th Annu. ACM-SIAM Symposium on Discrete Algorithms, pp. 801\u2013802 (2003)"},{"key":"9067_CR13","doi-asserted-by":"crossref","unstructured":"B\u0103doiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: Proc. 34th Annu. ACM Symposium on Theory Comput., pp. 250\u2013257 (2002)","DOI":"10.1145\/509907.509947"},{"key":"9067_CR14","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":"9067_CR15","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":"9067_CR16","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1145\/201019.201036","volume":"42","author":"K.L. Clarkson","year":"1995","unstructured":"Clarkson, K.L.: Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM 42, 488\u2013499 (1995)","journal-title":"J. ACM"},{"key":"9067_CR17","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K.L. Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.: Applications of random sampling in computational geometry,\u00a0II. Discrete Comput. Geom. 4, 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"9067_CR18","doi-asserted-by":"crossref","first-page":"1018","DOI":"10.1137\/S0097539793250287","volume":"24","author":"B. G\u00e4rtner","year":"1995","unstructured":"G\u00e4rtner, B.: A subexponential algorithm for abstract optimization problems. SIAM J. Comput. 24, 1018\u20131035 (1995)","journal-title":"SIAM J. Comput."},{"key":"9067_CR19","unstructured":"G\u00e4rtner, B.: Smallest enclosing ball\u2014fast and robust in C++. http:\/\/www.inf.ethz.ch\/personal\/gaertner\/miniball.html"},{"key":"9067_CR20","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1287\/opre.9.6.849","volume":"9","author":"P. Gilmore","year":"1961","unstructured":"Gilmore, P., Gomory, R.: A linear programming approach to the cutting-stock problem. Oper. Res. 9, 849\u2013859 (1961)","journal-title":"Oper. Res."},{"key":"9067_CR21","doi-asserted-by":"crossref","unstructured":"Har-Peled, S.: A replacement for Voronoi diagrams of near linear size. In: Proc. 42nd Annu. IEEE Sympos. Found. Comput. Sci., pp. 94\u2013103 (2001)","DOI":"10.1109\/SFCS.2001.959884"},{"key":"9067_CR22","unstructured":"Har-Peled, S.: A practical approach for computing the diameter of a point set (software). http:\/\/valis.cs.uiuc.edu\/~sariel\/research\/papers\/00\/diameter\/diam_prog.html"},{"key":"9067_CR23","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Kushal, A.: Smaller coresets for k-median and k-means clustering In: Proc. 21st Annu. Sympos. Comput. Geom., pp. 126\u2013134 (2005)","DOI":"10.1145\/1064092.1064114"},{"key":"9067_CR24","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mazumdar, S.: Coresets for k-means and k-median clustering and their applications. In: Proc. 36th Annu. ACM Sympos. Theory Comput., pp. 291\u2013300 (2004)","DOI":"10.1145\/1007352.1007400"},{"key":"9067_CR25","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":"9067_CR26","doi-asserted-by":"crossref","unstructured":"Kumar, P., Mitchell, J., Yildirim, E.: Approximate minimum enclosing balls in high dimensions using core-sets. ACM J. Exp. Algorithmics (online) 8 (2003)","DOI":"10.1145\/996546.996548"},{"key":"9067_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10957-005-2653-6","volume":"126","author":"P. Kumar","year":"2005","unstructured":"Kumar, P., Yildirim, E.: Minimum volume enclosing ellipsoids and core sets. J. Optim. Theory Appl. 126, 1\u201321 (2005)","journal-title":"J. Optim. Theory Appl."},{"key":"9067_CR28","unstructured":"Large geometric models archive: http:\/\/www.cc.gatech.edu\/projects\/large_models\/"},{"key":"9067_CR29","unstructured":"Mount, D., Arya, S.: ANN: library for approximate nearest neighbor searching. http:\/\/www.cs.umd.edu\/~mount\/ANN\/"},{"key":"9067_CR30","unstructured":"Todd, M.J., Yildirim, E.A.: On Khachiyan\u2019s algorithm for the computation of minimum volume enclosing ellipsoids. Technical report 1438, Cornell University (2005)"},{"key":"9067_CR31","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"A.C. Yao","year":"1982","unstructured":"Yao, A.C.: On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput. 11, 721\u2013736 (1982)","journal-title":"SIAM J. Comput."},{"key":"9067_CR32","doi-asserted-by":"crossref","first-page":"1339","DOI":"10.1137\/S0097539799363992","volume":"31","author":"Y. Zhou","year":"2002","unstructured":"Zhou, Y., Suri, S.: Algorithms for a minimum volume enclosing simplex in three dimensions. SIAM J. Comput. 31, 1339\u20131357 (2002)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9067-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9067-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9067-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:00Z","timestamp":1559137500000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9067-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,19]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,11]]}},"alternative-id":["9067"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9067-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,19]]}}}