{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:44:13Z","timestamp":1773798253894,"version":"3.50.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2011,6]]},"DOI":"10.1007\/s00454-011-9340-1","type":"journal-article","created":{"date-parts":[[2011,3,22]],"date-time":"2011-03-22T15:14:54Z","timestamp":1300806894000},"page":"596-616","source":"Crossref","is-referenced-by-count":148,"title":["k-means Requires Exponentially Many Iterations Even in the Plane"],"prefix":"10.1007","volume":"45","author":[{"given":"Andrea","family":"Vattani","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,3,23]]},"reference":[{"key":"9340_CR1","first-page":"155","volume-title":"Proceedings of the 23rd Symposium on Principles of Database Systems","author":"P.K. Agarwal","year":"2004","unstructured":"Agarwal, P.K., Mustafa, N.H.: k-means projective clustering. In: Proceedings of the 23rd Symposium on Principles of Database Systems, pp. 155\u2013165 (2004)"},{"key":"9340_CR2","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/1137856.1137880","volume-title":"Proceedings of the 22nd Annual Symposium on Computational Geometry","author":"D. Arthur","year":"2006","unstructured":"Arthur, D., Vassilvitskii, S.: How slow is the k-means method. In: Proceedings of the 22nd Annual Symposium on Computational Geometry, pp. 144\u2013153 (2006)"},{"issue":"2","key":"9340_CR3","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1137\/070683921","volume":"39","author":"D. Arthur","year":"2009","unstructured":"Arthur, D., Vassilvitskii, S.: Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method. SIAM J. Comput. 39(2), 766\u2013782 (2009)","journal-title":"SIAM J. Comput."},{"key":"9340_CR4","volume-title":"Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science","author":"D. Arthur","year":"2009","unstructured":"Arthur, D., Manthey, B., R\u00f6glin, H.: k-means has polynomial smoothed complexity. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (2009)"},{"key":"9340_CR5","unstructured":"Berkhin, P.: Survey of clustering data mining techniques. Technical report, Accrue Software, San Jose, CA, USA (2002)"},{"key":"9340_CR6","volume-title":"Pattern Classification","author":"R.O. Duda","year":"2000","unstructured":"Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Classification. Wiley, New York (2000)"},{"key":"9340_CR7","series-title":"Abstract in Biometrics","first-page":"768","volume-title":"Biometric Society Meeting","author":"E.W. Forgy","year":"1965","unstructured":"Forgy, E.W.: Cluster analysis of multivariate data: efficiency versus interpretability of classifications. In: Biometric Society Meeting, Riverside, California, 1965. Abstract in Biometrics, vol.\u00a021, p. 768 (1965)"},{"key":"9340_CR8","first-page":"281","volume-title":"Proceedings of the 4th Annual Hawaii International Conference on Statistics and Mathematics","author":"F. Gibou","year":"2005","unstructured":"Gibou, F., Fedkiw, R.: A fast hybrid k-means level set algorithm for segmentation. In: Proceedings of the 4th Annual Hawaii International Conference on Statistics and Mathematics, pp. 281\u2013291 (2005)"},{"issue":"3","key":"9340_CR9","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/s00453-004-1127-9","volume":"41","author":"S. Har-Peled","year":"2005","unstructured":"Har-Peled, S., Sadri, B.: How fast is the k-means method? Algorithmica 41(3), 185\u2013202 (2005)","journal-title":"Algorithmica"},{"issue":"6","key":"9340_CR10","first-page":"1199","volume":"E83-D","author":"M. Inaba","year":"2000","unstructured":"Inaba, M., Katoh, N., Imai, H.: Variance-based k-clustering algorithms by Voronoi diagrams and randomization. IEICE Trans. Inf. Syst. E83-D(6), 1199\u20131206 (2000)","journal-title":"IEICE Trans. Inf. Syst."},{"issue":"2\u20133","key":"9340_CR11","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/j.comgeo.2004.03.003","volume":"28","author":"T. Kanungo","year":"2004","unstructured":"Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.: A local search approximation algorithm for k-means clustering. Comput. Geom. 28(2\u20133), 89\u2013112 (2004)","journal-title":"Comput. Geom."},{"issue":"2","key":"9340_CR12","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S.P. Lloyd","year":"1982","unstructured":"Lloyd, S.P.: Least squares quantization in PCM. IEEE Trans. Inf. Theory 28(2), 129\u2013136 (1982)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9340_CR13","first-page":"281","volume-title":"Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability","author":"J.B. MacQueen","year":"1967","unstructured":"MacQueen, J.B.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, vol.\u00a01, pp. 281\u2013297 (1967)"},{"key":"9340_CR14","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1137\/1.9781611973068.51","volume-title":"Proceedings of the 20th Annual Symposium on Discrete Algorithms","author":"B. Manthey","year":"2009","unstructured":"Manthey, B., R\u00f6glin, H.: Improved smoothed analysis of the k-means method. In: Proceedings of the 20th Annual Symposium on Discrete Algorithms, pp. 461\u2013470 (2009)"},{"issue":"3","key":"9340_CR15","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"D.A. Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385\u2013463 (2004)","journal-title":"J. ACM"},{"key":"9340_CR16","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1145\/1542362.1542419","volume-title":"Proceedings of the 25th Annual Symposium on Computational Geometry","author":"A. Vattani","year":"2009","unstructured":"Vattani, A.: k-means requires exponentially many iterations even in the plane. In: Proceedings of the 25th Annual Symposium on Computational Geometry, pp. 324\u2013332. (2009)"},{"key":"9340_CR17","unstructured":"Vattani, A.: k-means lower bound implementation, www.cse.ucsd.edu\/~avattani\/k-means\/lowerbound.py"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s00454-011-9340-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T15:33:50Z","timestamp":1637422430000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-011-9340-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,23]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["9340"],"URL":"https:\/\/doi.org\/10.1007\/s00454-011-9340-1","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3,23]]}}}