{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:18:24Z","timestamp":1725549504593},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540240587"},{"type":"electronic","value":"9783540305385"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30538-5_27","type":"book-chapter","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T13:40:30Z","timestamp":1268401230000},"page":"324-335","source":"Crossref","is-referenced-by-count":16,"title":["No, Coreset, No Cry"],"prefix":"10.1007","author":[{"given":"Sariel","family":"Har-Peled","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1145\/299917.299918","volume":"30","author":"P.K. Agarwal","year":"1998","unstructured":"Agarwal, P.K., Sharir, M.: Efficient algorithms for geometric optimization. ACM Comput. Surv.\u00a030, 412\u2013458 (1998)","journal-title":"ACM Comput. Surv."},{"key":"27_CR2","unstructured":"Bern, M., Eppstein, D.: Approximation algorithms for geometric problems. In: Hochbaum, D.S. (ed.) Approximationg algorithms for NP-Hard problems., pp. 296\u2013345. PWS Publishing Company (1997)"},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"1714","DOI":"10.1137\/S0097539794265724","volume":"26","author":"P.K. Agarwal","year":"1997","unstructured":"Agarwal, P.K., Aronov, B., Sharir, M.: Computing envelopes in four dimensions with applications. SIAM J. Comput.\u00a026, 1714\u20131732 (1997)","journal-title":"SIAM J. Comput."},{"key":"27_CR4","doi-asserted-by":"publisher","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.\u00a016, 317\u2013337 (1996)","journal-title":"Discrete Comput. Geom."},{"key":"27_CR5","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1006\/jagm.1994.1038","volume":"17","author":"P.K. Agarwal","year":"1994","unstructured":"Agarwal, P.K., Sharir, M., Toledo, S.: Applications of parametric searching in geometric optimization. J. Algorithms\u00a017, 292\u2013318 (1994)","journal-title":"J. Algorithms"},{"key":"27_CR6","unstructured":"Ebara, H., Fukuyama, N., Nakano, H., Nakanishi, Y.: Roundness algorithms using the Voronoi diagrams. In: Proc. 1st Canad. Conf. Comput. Geom., p. 41 (1989)"},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Guibas, L.J., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM J. Comput.\u00a015, 317\u2013340 (1986)","journal-title":"SIAM J. Comput."},{"key":"27_CR8","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/PL00009392","volume":"20","author":"J. Garc\u00eda-Lopez","year":"1998","unstructured":"Garc\u00eda-Lopez, J., Ramos, P., Snoeyink, J.: Fitting a set of points by a circle. Discrete Comput. Geom.\u00a020, 389\u2013402 (1998)","journal-title":"Discrete Comput. Geom."},{"key":"27_CR9","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1109\/34.75510","volume":"13","author":"V.B. Le","year":"1991","unstructured":"Le, V.B., Lee, D.T.: Out-of-roundness problem revisited. IEEE Trans. Pattern Anal. Mach. Intell. PAMI\u00a013, 217\u2013223 (1991)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell. PAMI"},{"key":"27_CR10","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K., Shermer, T.C., Yap, C.K.: A complete roundness classification procedure. In: Proc. 13th Annu. ACM Sympos. Comput. Geom., pp. 129\u2013138 (1997)","DOI":"10.1145\/262839.262917"},{"key":"27_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985)"},{"key":"27_CR12","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/BF02253130","volume":"21","author":"T.J. Rivlin","year":"1979","unstructured":"Rivlin, T.J.: Approximating by circles. Computing\u00a021, 93\u2013104 (1979)","journal-title":"Computing"},{"key":"27_CR13","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1016\/0010-4485(91)90045-X","volume":"23","author":"U. Roy","year":"1991","unstructured":"Roy, U., Liu, C.R., Woo, T.C.: Review of dimensioning and tolerancing: Representation and processing. Comput. Aided Design\u00a023, 466\u2013483 (1991)","journal-title":"Comput. Aided Design"},{"key":"27_CR14","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0010-4485(92)90035-9","volume":"24","author":"U. Roy","year":"1992","unstructured":"Roy, U., Zhang, X.: Establishment of a pair of concentric circles with the minimum radial separation for assessing roundness error. Comput. Aided Design\u00a024, 161\u2013168 (1992)","journal-title":"Comput. Aided Design"},{"key":"27_CR15","unstructured":"Shermer, T.C., Yap, C.K.: Probing for near centers and relative roundness. In: Proc. ASME Workshop on Tolerancing and Metrology (1995)"},{"key":"27_CR16","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1142\/S021819599900008X","volume":"9","author":"M. Smid","year":"1999","unstructured":"Smid, M., Janardan, R.: On the width and roundness of a set of points in the plane. Internat. J. Comput. Geom. Appl.\u00a09, 97\u2013108 (1999)","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"27_CR17","first-page":"393","volume-title":"Robotics Motion and Manipulation","author":"C.K. Yap","year":"1997","unstructured":"Yap, C.K., Chang, E.C.: Issues in the metrology of geometric tolerancing. In: Laumond, J.P., Overmars, M.H. (eds.) Robotics Motion and Manipulation, pp. 393\u2013400. A. K. Peters, Wellesley (1997)"},{"key":"27_CR18","doi-asserted-by":"publisher","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. Internat. J. Comput. Geom. Appl.\u00a012, 67\u201385 (2002)","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"27_CR19","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1007\/s4540010062","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.\u00a024, 687\u2013705 (2000)","journal-title":"Discrete Comput. Geom."},{"key":"27_CR20","doi-asserted-by":"publisher","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\u00a051, 606\u2013635 (2004)","journal-title":"J. ACM"},{"key":"27_CR21","doi-asserted-by":"publisher","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. Theoret. Comput. Sci.\u00a038, 293\u2013306 (1985)","journal-title":"Theoret. Comput. Sci."},{"key":"27_CR22","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s00453-001-0110-y","volume":"33","author":"P.K. Agarwal","year":"2002","unstructured":"Agarwal, P.K., Procopiuc, C.M.: Exact and approximation algorithms for clustering. Algorithmica\u00a033, 201\u2013226 (2002)","journal-title":"Algorithmica"},{"key":"27_CR23","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Procopiuc, C.M., Varadarajan, K.R.: Approximation algorithms for k-line center. In: Proc. 10th Annu. European Sympos. Algorithms, pp. 54\u201363 (2002)","DOI":"10.1007\/3-540-45749-6_9"},{"key":"27_CR24","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0747-7171(08)80067-3","volume":"10","author":"N. Megiddo","year":"1990","unstructured":"Megiddo, N.: On the complexity of some geometric problems in unbounded dimension. J. Symb. Comput.\u00a010, 327\u2013334 (1990)","journal-title":"J. Symb. Comput."},{"key":"27_CR25","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s00454-004-1118-2","volume":"32","author":"S. Har-Peled","year":"2004","unstructured":"Har-Peled, S., Varadarajan, K.R.: High-dimensional shape fitting in linear time. Discrete Comput. Geom.\u00a032, 269\u2013288 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"27_CR26","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/0167-6377(82)90039-6","volume":"1","author":"N. Megiddo","year":"1982","unstructured":"Megiddo, N., Tamir, A.: On the complexity of locating linear facilities in the plane. Oper. Res. Lett.\u00a01, 194\u2013197 (1982)","journal-title":"Oper. Res. Lett."},{"key":"27_CR27","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":"27_CR28","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Varadarajan, K.R.: Projective clustering in high dimensions using core-sets. In: Proc. 18th Annu. ACM Sympos. Comput. Geom., pp. 312\u2013318 (2002)","DOI":"10.1145\/513400.513440"},{"key":"27_CR29","doi-asserted-by":"crossref","unstructured":"B\u0103doiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: Proc. 34th Annu. ACM Sympos. Theory Comput., pp. 250\u2013257 (2002)","DOI":"10.1145\/509943.509947"},{"key":"27_CR30","unstructured":"Kumar, P., Mitchell, J.S.B., Yildirim, E.A.: Fast smallest enclosing hypersphere computation. In: Proc. 5th Workshop Algorithm Eng. Exper. (2003)(to appear)"},{"key":"27_CR31","doi-asserted-by":"publisher","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.\u00a033, 269\u2013285 (2004)","journal-title":"SIAM J. Comput."},{"key":"27_CR32","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.\u00a031, 545\u2013565 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"27_CR33","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1109\/34.6790","volume":"10","author":"M.E. Houle","year":"1988","unstructured":"Houle, M.E., Toussaint, G.T.: Computing the width of a set. IEEE Trans. Pattern Anal. Mach. Intell. PAMI\u00a010, 761\u2013765 (1988)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell. PAMI"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30538-5_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:58:50Z","timestamp":1605761930000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30538-5_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540240587","9783540305385"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30538-5_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}