{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T16:59:17Z","timestamp":1782233957519,"version":"3.54.5"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T00:00:00Z","timestamp":1761523200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T00:00:00Z","timestamp":1761523200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005713","name":"Technische Universit\u00e4t M\u00fcnchen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005713","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2026,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We construct small coresets for weight-constrained anisotropic assignment and clustering with a specific view toward applications in materials science. Building on previous results for unconstrained least-squares clustering of Har-Peled &amp; Kushal, we obtain coresets even for weight-constrained anisotropic clustering and, particularly, reduce the dependence of their sizes on the number of clusters from cubic to quadratic, an improvement which is decisive for applications in small dimensions such as grain mapping.<\/jats:p>","DOI":"10.1007\/s00454-025-00754-1","type":"journal-article","created":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T20:28:36Z","timestamp":1761596916000},"page":"378-415","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Coresets for Weight-Constrained Anisotropic Assignment and Clustering"],"prefix":"10.1007","volume":"76","author":[{"given":"Maximilian","family":"Fiedler","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0157-6880","authenticated-orcid":false,"given":"Peter","family":"Gritzmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,10,27]]},"reference":[{"key":"754_CR1","doi-asserted-by":"crossref","unstructured":"Brieden, A., Gritzmann, P.: A quadratic optimization model for the consolidation of farmland by means of lend-lease agreements. In: Ahr, D., Fahrion, R., Oswald, M., and Reinelt, G., (eds), Operations Research Proceedings 2003, pp 324\u2013331. Springer, Berlin, Heidelberg, (2004)","DOI":"10.1007\/978-3-642-17022-5_42"},{"issue":"1","key":"754_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12351-009-0041-y","volume":"11","author":"S Borgwardt","year":"2011","unstructured":"Borgwardt, S., Brieden, A., Gritzmann, P.: Constrained minimum-k-star clustering and its application to the consolidation of farmland. Oper. Res. Int. J. 11(1), 1\u201317 (2011)","journal-title":"Oper. Res. Int. J."},{"issue":"2","key":"754_CR3","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1137\/110832707","volume":"26","author":"A Brieden","year":"2012","unstructured":"Brieden, A., Gritzmann, P.: On optimal weighted balanced clusterings: Gravity bodies and power diagrams. SIAM J. Discret. Math. 26(2), 415\u2013434 (2012)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"754_CR4","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s00283-014-9448-2","volume":"36","author":"S Borgwardt","year":"2014","unstructured":"Borgwardt, S., Brieden, A., Gritzmann, P.: Geometric clustering for the consolidation of farmland and woodland. Math. Intell. 36(2), 37\u201344 (2014)","journal-title":"Math. Intell."},{"issue":"9","key":"754_CR5","doi-asserted-by":"publisher","first-page":"1016","DOI":"10.1080\/14786435.2015.1015469","volume":"95","author":"A Alpers","year":"2015","unstructured":"Alpers, A., Brieden, A., Gritzmann, P., Lyckegaard, A., Poulsen, H.F.: Generalized balanced power diagrams for 3D representations of polycrystals. Phil. Mag. 95(9), 1016\u20131028 (2015)","journal-title":"Phil. Mag."},{"key":"754_CR6","unstructured":"Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvitskii, S.: Fair clustering through fairlets. In: Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS\u201917, pages 5036\u20135044, Red Hook, NY, USA, Curran Associates Inc (2017)"},{"issue":"1","key":"754_CR7","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.ejor.2017.04.018","volume":"263","author":"A Brieden","year":"2017","unstructured":"Brieden, A., Gritzmann, P., Klemm, F.: Constrained clustering via diagrams: A unified theory and its application to electoral district design. Eur. J. Oper. Res. 263(1), 18\u201334 (2017)","journal-title":"Eur. J. Oper. Res."},{"key":"754_CR8","unstructured":"Huang, L., Jiang, S. H.-C., Vishnoi, N.\u00a0K.: Coresets for clustering with fairness constraints. In: Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp 7589\u2013 7600, Red Hook, NY, USA, Curran Associates Inc (2019)"},{"key":"754_CR9","doi-asserted-by":"crossref","unstructured":"Schmidt, M., Schwiegelshohn, C., Sohler, C.: Fair coresets and streaming algorithms for fair k-means. In: Bamis, E. and Megow, N., (eds) Approximation and Online Algorithms, Lecture Notes in Computer Science 11926, pp 232\u2013251. Springer, (2020)","DOI":"10.1007\/978-3-030-39479-0_16"},{"key":"754_CR10","doi-asserted-by":"publisher","unstructured":"Brieden, A., Gritzmann, P.: Predicting show rates in air cargo transport. In: International Conference on Artificial Intelligence and Data Analytics for Air Transportation (AIDA-AT), pp 1\u20139, Singapore, IEEE. (2020) https:\/\/doi.org\/10.1109\/AIDA-AT48540.2020.9049209.","DOI":"10.1109\/AIDA-AT48540.2020.9049209."},{"key":"754_CR11","unstructured":"Brieden, A., Gritzmann, P.: Response prediction: Gaining reliable and interpretable insight from small study data. Technical report, (2022)"},{"key":"754_CR12","volume-title":"Constrained clustering: advances in algorithms, theory, and applications","year":"2009","unstructured":"Basu, S., Davidson, I., Wagstaff, K.L. (eds.): Constrained clustering: advances in algorithms, theory, and applications. CRC Press, Boca Raton (2009)"},{"key":"754_CR13","first-page":"937","volume-title":"CRC handbook on discrete and computational geometry","author":"P Gritzmann","year":"2017","unstructured":"Gritzmann, P.: Klee, Victor: Computational convexity. In: O'Rourke, J., Goodman, J.E., T\u00f3th, C.D. (eds.) CRC handbook on discrete and computational geometry, pp. 937\u2013968. CRC Press, Boca Raton (2017)"},{"issue":"1","key":"754_CR14","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/22M1491988","volume":"16","author":"A Alpers","year":"2023","unstructured":"Alpers, A., Fiedler, M., Gritzmann, P., Klemm, F.: Turning grain maps into diagrams. SIAM J. Imag. Sci. 16(1), 223\u2013249 (2023)","journal-title":"SIAM J. Imag. Sci."},{"issue":"1","key":"754_CR15","doi-asserted-by":"publisher","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. Discret. Comput. Geom. 37(1), 3\u201319 (2007)","journal-title":"Discret. Comput. Geom."},{"key":"754_CR16","doi-asserted-by":"crossref","unstructured":"Feldman, D., Schmidt, M., Sohler, C.: Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1434\u20131453, Philadelphia, PA, Society for Industrial and Applied Mathematics (2013)","DOI":"10.1137\/1.9781611973105.103"},{"key":"754_CR17","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1137\/18M1209854","volume":"49","author":"D Feldman","year":"2020","unstructured":"Feldman, D., Schmidt, M., Sohler, C.: Turning big data into tiny data: Constant-size coresets for $$k$$-means, PCA, and projective clustering. SIAM J. Comput. 49, 601\u2013657 (2020)","journal-title":"SIAM J. Comput."},{"key":"754_CR18","doi-asserted-by":"crossref","unstructured":"Fichtenberger, H., Gill\u00e9, M., Schmidt, M., Schwiegelshohn, C., Sohler, C.: BICO: BIRCH meets coresets for k-means clustering. In: Bodlaender, H.L. and, Italiano, G.F. (eds.) Algorithms - ESA 2013. Lecture Notes in Computer Science 8125, pp. 481\u2013492. Springer, Berlin, Heidelberg (2013)","DOI":"10.1007\/978-3-642-40450-4_41"},{"key":"754_CR19","doi-asserted-by":"crossref","unstructured":"Sohler, C., Woodruff, D.\u00a0P.: Strong coresets for k-median and subspace approximation: Goodbye dimension. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp 802\u2013813. IEEE, (2018)","DOI":"10.1109\/FOCS.2018.00081"},{"key":"754_CR20","unstructured":"Bachem, O., Lucic, M., Krause, A.: Practical coreset constructions for machine learning. Technical report, (2017). arxiv:1703.06476"},{"key":"754_CR21","doi-asserted-by":"crossref","unstructured":"Cohen, M.\u00a0B., Elder, S., Musco, C., Musco, Ch, and Persu, M.: Dimensionality reduction for k-means clustering and low rank approximation. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing - STOC \u201915, pp 163\u2013172, New York, ACM Press (2015)","DOI":"10.1145\/2746539.2746569"},{"key":"754_CR22","unstructured":"Fiedler, M.: Fast Constrained Clustering of Big Data: Theory and Application to Grain Mapping. PhD thesis, Technische Universit\u00e4t M\u00fcnchen, (2024)"},{"key":"754_CR23","unstructured":"Bandyapadhyay, S., Fomin, F.\u00a0V., Simonov, K.: On coresets for fair clustering in metric and Euclidean spaces and their applications. In: Bansal, N., Merelli, E, and Worrell, J.(eds.) 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pp 23:1\u201323:15. Dagstuhl Publishing, (2021)"},{"key":"754_CR24","doi-asserted-by":"crossref","unstructured":"Feldman, D., Langberg, M.: A unified framework for approximating and clustering data. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing - STOC \u201911, pp 569\u2013578, New York, ACM Press (2011)","DOI":"10.1145\/1993636.1993712"},{"key":"754_CR25","unstructured":"Dasgupta, S.: The hardness of k-means clustering. Technical report, CS2007-0890, University of California, San Diego, (2007)"},{"issue":"2","key":"754_CR26","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s10994-009-5103-0","volume":"75","author":"D Aloise","year":"2009","unstructured":"Aloise, D., Deshpande, A., Hansen, P., Popat, P.: NP-hardness of Euclidean sum-of-squares clustering. Mach. Learn. 75(2), 245\u2013248 (2009)","journal-title":"Mach. Learn."},{"key":"754_CR27","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2010.05.034","volume":"442","author":"M Mahajan","year":"2012","unstructured":"Mahajan, M., Nimbhorkar, P., Varadarajan, K.: The planar k-means problem is NP-hard. Theoret. Comput. Sci. 442, 13\u201321 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"754_CR28","unstructured":"Awasthi, P., Charikar, M., Krishnaswamy, R., Sinop, A.\u00a0K.: The hardness of approximation of Euclidean k-means. In: 31st International Symposium on Computational Geometry (SoCG 2015), volume\u00a034, pp 754\u2013767, (2015)"},{"key":"754_CR29","unstructured":"Braverman, V., Feldman, D., Lang, H.: New frameworks for offline and streaming coreset constructions. Technical report, (2016). arxiv:1612.00889"},{"key":"754_CR30","doi-asserted-by":"crossref","unstructured":"Makarychev, K., Makarychev, Y., Razenshteyn, I.: Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019, pp 1027\u20131038, New York, (2019). ACM Press","DOI":"10.1145\/3313276.3316350"},{"issue":"3","key":"754_CR31","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1137\/070699007","volume":"39","author":"K Chen","year":"2009","unstructured":"Chen, K.: On coresets for k-median and k-means clustering in metric and Euclidean spaces and their applications. SIAM J. Comput. 39(3), 923\u2013947 (2009)","journal-title":"SIAM J. Comput."},{"key":"754_CR32","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.schres.2023.08.026","volume":"260","author":"D Sch\u00f6ttle","year":"2023","unstructured":"Sch\u00f6ttle, D., Wiedemann, K., Correll, C.U., Janetzky, W., Friede, M., Jahn, H., Brieden, A.: Response prediction in treatment of patients with schizophrenia after switching from oral aripiprazole to aripiprazole once-monthly. Schizophr. Res. 260, 183\u2013190 (2023)","journal-title":"Schizophr. Res."},{"key":"754_CR33","volume-title":"Geometry analysis and convexity","author":"P Gritzmann","year":"2025","unstructured":"Gritzmann, P.: Constrained, clustering, diagrams, coresets and their applications. In: Alonso Guti\u00e9rrez, D., Gonz\u00e1les Merino, B, Jim\u00e9nez, and Villa, R. (eds.) Geometry analysis and convexity. Springer, Berlin (2025)"},{"key":"754_CR34","doi-asserted-by":"publisher","DOI":"10.1007\/b97884","volume-title":"Three-dimensional x-ray diffraction microscopy: mapping polycrystals and their dynamics","author":"HF Poulsen","year":"2004","unstructured":"Poulsen, H.F.: Three-dimensional x-ray diffraction microscopy: mapping polycrystals and their dynamics. Springer, Berlin (2004)"},{"key":"754_CR35","volume-title":"Advanced tomographic methods in materials research and engineering","year":"2008","unstructured":"Banhart, J. (ed.): Advanced tomographic methods in materials research and engineering. Oxford University Press, Oxford (2008)"},{"key":"754_CR36","doi-asserted-by":"publisher","first-page":"301","DOI":"10.4028\/www.scientific.net\/MSF.94-96.301","volume":"94\u201396","author":"H Telley","year":"1992","unstructured":"Telley, H., Liebling, T.M., Mocellin, A., Righetti, F.: Simulating and modelling grain growth as the motion of a weighted Voronoi diagram. Mater. Sci. Forum 94\u201396, 301\u2013306 (1992)","journal-title":"Mater. Sci. Forum"},{"issue":"4","key":"754_CR37","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1080\/14786430802647065","volume":"89","author":"X Tingting","year":"2009","unstructured":"Xu, T., Li, M.: Topological and statistical properties of a constrained Voronoi tessellation. Phil. Mag. 89(4), 349\u2013374 (2009)","journal-title":"Phil. Mag."},{"issue":"4","key":"754_CR38","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1080\/13642819708202339","volume":"75","author":"X Xue","year":"1997","unstructured":"Xue, X., Righetti, F., Telley, H., Liebling, T.L.: The Laguerre model for grain growth in three dimensions. Phil. Mag. B 75(4), 567\u2013585 (1997)","journal-title":"Philosophical Magazine B"},{"issue":"3","key":"754_CR39","doi-asserted-by":"publisher","DOI":"10.1063\/1.2959733","volume":"93","author":"M K\u00fchn","year":"2008","unstructured":"K\u00fchn, M., Steinhauser, M.O.: Modeling and simulation of microstructures using power diagrams: Proof of the concept. Appl. Phys. Lett. 93(3), 034102 (2008)","journal-title":"Appl. Phys. Lett."},{"issue":"3","key":"754_CR40","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1002\/adem.201000258","volume":"13","author":"A Lyckegaard","year":"2011","unstructured":"Lyckegaard, A., Lauridsen, E.M., Ludwig, W., Fonda, R.W., Poulsen, H.F.: On the use of Laguerre tessellations for representations of 3D grain structures. Adv. Eng. Mater. 13(3), 165\u2013170 (2011)","journal-title":"Adv. Eng. Mater."},{"issue":"4","key":"754_CR41","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1007\/s10955-013-0893-7","volume":"154","author":"A Spettl","year":"2014","unstructured":"Spettl, A., Werz, T., Krill III, C.E., Schmidt, V.: Parametric representation of 3D grain ensembles in polycrystalline microstructures. J. Stat. Phys. 154(4), 913\u2013928 (2014)","journal-title":"J. Stat. Phys."},{"key":"754_CR42","doi-asserted-by":"publisher","first-page":"121","DOI":"10.5566\/ias.v33.p121-130","volume":"33","author":"H Altendorf","year":"2014","unstructured":"Altendorf, H., Latourte, F., Jeulin, D., Faessel, M., Saintoyant, L.: 3D reconstruction of multiscale microstructure by anisotropic tesselation models. Image Analy. Stereol. 33, 121\u2013130 (2014)","journal-title":"Image Analy. Stereol."},{"key":"754_CR43","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.commatsci.2015.02.006","volume":"102","author":"K Teferra","year":"2015","unstructured":"Teferra, K., Graham-Brady, L.: Tessellation growth models for polycrystalline microstructures. Comput. Mater. Sci. 102, 57\u201367 (2015)","journal-title":"Comput. Mater. Sci."},{"issue":"25","key":"754_CR44","doi-asserted-by":"publisher","first-page":"2777","DOI":"10.1080\/14786435.2015.1078511","volume":"95","author":"A Liebscher","year":"2015","unstructured":"Liebscher, A.: Laguerre approximation of random foams. Phil. Mag. 95(25), 2777\u20132792 (2015)","journal-title":"Phil. Mag."},{"key":"754_CR45","doi-asserted-by":"crossref","unstructured":"Labelle, F., Shewchuk, J.\u00a0R.: Anisotropic Voronoi diagrams and guaranteed-quality anisotropic mesh generation. In: Proceedings of the 19th Annual Symposium on Computational Geometry (SCG \u201903), pp 191\u2013200. ACM Press, (2003)","DOI":"10.1145\/777792.777822"},{"issue":"2\u20133","key":"754_CR46","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.tcs.2008.08.006","volume":"408","author":"J-D Boissonnat","year":"2008","unstructured":"Boissonnat, J.-D., Wormser, C., Yvinec, M.: Anisotropic diagrams: the Labelle Shewchuk approach revisited. Theoret. Comput. Sci. 408(2\u20133), 163\u2013173 (2008)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"754_CR47","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1080\/14786435.2015.1125540","volume":"96","author":"A Spettl","year":"2016","unstructured":"Spettl, A., Brereton, T., Duan, Q., Werz, T., Krill III, C.E., Kroese, D.P., Schmidt, V.: Fitting Laguerre tessellation approximations to tomographic image data. Phil. Mag. 96(2), 166\u2013189 (2016)","journal-title":"Phil. Mag."},{"issue":"18","key":"754_CR48","doi-asserted-by":"publisher","first-page":"1926","DOI":"10.1080\/14786435.2016.1183829","volume":"96","author":"O \u0160ediv\u00fd","year":"2016","unstructured":"\u0160ediv\u00fd, O., Brereton, T., Westhoff, D., Pol\u00edvka, L., Bene\u0161, V., Schmidt, V., J\u00e4ger, A.: 3D reconstruction of grains in polycrystalline materials using a tessellation model with curved grain boundaries. Phil. Mag. 96(18), 1926\u20131949 (2016)","journal-title":"Phil. Mag."},{"issue":"1","key":"754_CR49","doi-asserted-by":"publisher","first-page":"5","DOI":"10.5566\/ias.1656","volume":"36","author":"O \u0160ediv\u00fd","year":"2017","unstructured":"\u0160ediv\u00fd, O., Dake, J.M., Krill III, C.E., Schmidt, V., J\u00e4ger, A.: Description of the 3D morphology of grain boundaries in aluminum alloys using tessellation models generated by ellipsoids. Image Analy. Stereol. 36(1), 5\u201313 (2017)","journal-title":"Image Analy. Stereol."},{"key":"754_CR50","doi-asserted-by":"publisher","DOI":"10.3389\/fmats.2021.760602","volume":"8","author":"L Petrich","year":"2021","unstructured":"Petrich, L., Furat, O., Wang, M., Krill III, C.E., Schmidt, V.: Efficient fitting of 3D tessellations to curved polycrystalline grain boundaries. Front. Mater. 8, 760602 (2021)","journal-title":"Front. Mater."},{"issue":"2","key":"754_CR51","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1080\/09500839.2018.1472399","volume":"98","author":"K Teferra","year":"2018","unstructured":"Teferra, K., Rowenhorst, D.J.: Direct parameter estimation for generalised balanced power diagrams. Phil. Mag. Lett. 98(2), 79\u201387 (2018)","journal-title":"Philos. Mag. Lett."},{"issue":"103","key":"754_CR52","doi-asserted-by":"publisher","first-page":"948","DOI":"10.1080\/14786435.2023.2180679","volume":"10","author":"A Alpers","year":"2023","unstructured":"Alpers, A., Fiedler, M., Gritzmann, P., Klemm, F.: Dynamic grain models via fast heuristics for diagram representations. Phil. Mag. 10(103), 948\u2013968 (2023)","journal-title":"Phil. Mag."},{"key":"754_CR53","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-642-03685-9_2","volume-title":"Approximation, randomization, and combinatorial optimization","author":"A Aggarwal","year":"2009","unstructured":"Aggarwal, A., Deshpande, A., Kannan, R.: Adaptive sampling for k-means clustering. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) Approximation, randomization, and combinatorial optimization. Algorithms and techniques, Lecture Notes in Computer Science 5687, pp. 15\u201328. Springer, Berlin, Heidelberg (2009)"},{"key":"754_CR54","doi-asserted-by":"publisher","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. Geometry Theory Appl. 28, 89\u2013112 (2004)","journal-title":"Comput. Geometry Theory Appl."},{"key":"754_CR55","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002)","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"754_CR56","volume-title":"Davenport-Schinzel sequences and their geometric applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel sequences and their geometric applications. Cambridge University Press, Cambridge (1995)"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00754-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-025-00754-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00754-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T16:41:51Z","timestamp":1782232911000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-025-00754-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,27]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,7]]}},"alternative-id":["754"],"URL":"https:\/\/doi.org\/10.1007\/s00454-025-00754-1","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,27]]},"assertion":[{"value":"9 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 June 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}