{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T12:48:26Z","timestamp":1778244506024,"version":"3.51.4"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T00:00:00Z","timestamp":1675123200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,1,31]]},"abstract":"<jats:p>\n            In 2015, Driemel, Krivo\u0161ija, and Sohler introduced the\n            <jats:italic>k,\u2113<\/jats:italic>\n            -median clustering problem for polygonal curves under the Fr\u00e9chet distance. Given a set of input curves, the problem asks to find\n            <jats:italic>k<\/jats:italic>\n            median curves of at most \u2113 vertices each that minimize the sum of Fr\u00e9chet distances over all input curves to their closest median curve. A major shortcoming of their algorithm is that the input curves are restricted to lie on the real line. In this article, we present a randomized bicriteria-approximation algorithm that works for polygonal curves in \u211d\n            <jats:italic>\n              <jats:sup>d<\/jats:sup>\n            <\/jats:italic>\n            and achieves approximation factor (1+\u025b) with respect to the clustering costs. The algorithm has worst-case running time linear in the number of curves, polynomial in the maximum number of vertices per curve (i.e., their complexity), and exponential in\n            <jats:italic>d<\/jats:italic>\n            , \u2113, 1\/\u025b and 1\/\u03b4 (i.e.,\u00a0the failure probability). We achieve this result through a shortcutting lemma, which guarantees the existence of a polygonal curve with similar cost as an optimal median curve of complexity \u2113, but of complexity at most 2\u2113 -2, and whose vertices can be computed efficiently. We combine this lemma with the superset sampling technique by Kumar et\u00a0al. to derive our clustering result. In doing so, we describe and analyze a generalization of the algorithm by Ackermann et\u00a0al., which may be of independent interest.\n          <\/jats:p>","DOI":"10.1145\/3559764","type":"journal-article","created":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T12:38:07Z","timestamp":1661949487000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Approximating (\n            <i>k,\u2113<\/i>\n            )-Median Clustering for Polygonal Curves"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3446-4343","authenticated-orcid":false,"given":"Maike","family":"Buchin","sequence":"first","affiliation":[{"name":"Ruhr University Bochum"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1943-2589","authenticated-orcid":false,"given":"Anne","family":"Driemel","sequence":"additional","affiliation":[{"name":"University of Bonn"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8984-1962","authenticated-orcid":false,"given":"Dennis","family":"Rohde","sequence":"additional","affiliation":[{"name":"Ruhr University Bochum"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,2,23]]},"reference":[{"issue":"3","key":"e_1_3_1_2_2","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1111\/1467-9469.00350","article-title":"Unsupervised curve clustering using B-splines","volume":"30","author":"Abraham C.","year":"2003","unstructured":"C. Abraham, P. A. Cornillon, E. Matzner-L\u00f8ber, and N. Molinari. 2003. Unsupervised curve clustering using B-splines. Scandinavian Journal of Statistics 30, 3 (2003), 581\u2013595.","journal-title":"Scandinavian Journal of Statistics"},{"issue":"4","key":"e_1_3_1_3_2","first-page":"Article 59, 26","article-title":"Clustering for metric and nonmetric distance measures","volume":"6","author":"Ackermann Marcel R.","year":"2010","unstructured":"Marcel R. Ackermann, Johannes Bl\u00f6mer, and Christian Sohler. 2010. Clustering for metric and nonmetric distance measures. ACM Transactions on Algorithms 6, 4 (2010), Article 59, 26 pages.","journal-title":"ACM Transactions on Algorithms"},{"key":"e_1_3_1_4_2","first-page":"29","volume-title":"Algorithms\u2014","author":"Agarwal Pankaj K.","year":"2002","unstructured":"Pankaj K. Agarwal, Sariel Har-Peled, Nabil H. Mustafa, and Yusu Wang. 2002. Near-linear time approximation algorithms for curve simplification. In Algorithms\u2014, Rolf M\u00f6hring and Rajeev Raman (Eds.). Springer, 29\u201341."},{"key":"e_1_3_1_5_2","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1142\/S0218195995000064","article-title":"Computing the Fr\u00e9chet distance between two polygonal curves","volume":"5","author":"Alt Helmut","year":"1995","unstructured":"Helmut Alt and Michael Godau. 1995. Computing the Fr\u00e9chet distance between two polygonal curves. International Journal of Computational Geometry & Applications 5 (1995), 75\u201391.","journal-title":"International Journal of Computational Geometry & Applications"},{"key":"e_1_3_1_6_2","first-page":"1705","article-title":"Clustering with Bregman divergences","volume":"6","author":"Banerjee Arindam","year":"2005","unstructured":"Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, and Joydeep Ghosh. 2005. Clustering with Bregman divergences. Journal of Machine Learning Research 6 (2005), 1705\u20131749.","journal-title":"Journal of Machine Learning Research"},{"issue":"1","key":"e_1_3_1_7_2","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","article-title":"Correlation clustering","volume":"56","author":"Bansal Nikhil","year":"2004","unstructured":"Nikhil Bansal, Avrim Blum, and Shuchi Chawla. 2004. Correlation clustering. Machine Learning 56, 1\u20133 (2004), 89\u2013113.","journal-title":"Machine Learning"},{"key":"e_1_3_1_8_2","first-page":"125","article-title":"Support vector clustering","volume":"2","author":"Ben-Hur Asa","year":"2001","unstructured":"Asa Ben-Hur, David Horn, Hava T. Siegelmann, and Vladimir Vapnik. 2001. Support vector clustering. Journal of Machine Learning Research 2 (2001), 125\u2013137.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_1_9_2","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1145\/3397536.3422245","volume-title":"SIGSPATIAL\u201920: 28th International Conference on Advances in Geographic Information Systems, Seattle, WA, USA, November 3\u20136, 2020","author":"Brankovic Milutin","year":"2020","unstructured":"Milutin Brankovic, Kevin Buchin, Koen Klaren, Andr\u00e9 Nusser, Aleksandr Popov, and Sampson Wong. 2020. (k, l)-medians clustering of trajectories using continuous dynamic time warping. In SIGSPATIAL\u201920: 28th International Conference on Advances in Geographic Information Systems, Seattle, WA, USA, November 3\u20136, 2020, Chang-Tien Lu, Fusheng Wang, Goce Trajcevski, Yan Huang, Shawn D. Newsam, and Li Xiong (Eds.). ACM, New York, NY, 99\u2013110."},{"issue":"1","key":"e_1_3_1_10_2","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.comgeo.2007.08.003","article-title":"Computing the Fr\u00e9chet distance between simple polygons","volume":"41","author":"Buchin Kevin","year":"2008","unstructured":"Kevin Buchin, Maike Buchin, and Carola Wenk. 2008. Computing the Fr\u00e9chet distance between simple polygons. Computational Geometry 41, 1\u20132 (2008), 2\u201320.","journal-title":"Computational Geometry"},{"key":"e_1_3_1_11_2","doi-asserted-by":"crossref","first-page":"2922","DOI":"10.1137\/1.9781611975482.181","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Buchin Kevin","year":"2019","unstructured":"Kevin Buchin, Anne Driemel, Joachim Gudmundsson, Michael Horton, Irina Kostitsyna, Maarten L\u00f6ffler, and Martijn Struijs. 2019. Approximating (k, l)-center clustering for curves. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms. 2922\u20132938."},{"key":"e_1_3_1_12_2","volume-title":"Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory.","author":"Buchin Kevin","year":"2020","unstructured":"Kevin Buchin, Anne Driemel, and Martijn Struijs. 2020. On the hardness of computing an average curve. In Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory. Article 19, 19 pages."},{"key":"e_1_3_1_13_2","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1145\/3347146.3359111","volume-title":"Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems","author":"Buchin Kevin","year":"2019","unstructured":"Kevin Buchin, Anne Driemel, Natasja van de L\u2019Isle, and Andr\u00e9 Nusser. 2019. klcluster: Center-based clustering of trajectories. In Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 496\u2013499."},{"key":"e_1_3_1_14_2","doi-asserted-by":"crossref","unstructured":"Maike Buchin and Dennis Rohde. 2022. Coresets for  \\((k \\ell)\\) -median clustering under the Fr\u00e9chet distance. In Algorithms and Discrete Applied Mathematics . Lecture Notes in Computer Science Vol. 13179. Springer 167\u2013180.","DOI":"10.1007\/978-3-030-95018-7_14"},{"issue":"4","key":"e_1_3_1_15_2","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1111\/j.1467-9868.2007.00605.x","article-title":"Functional clustering and identifying substructures of longitudinal data","volume":"69","author":"Chiou Jeng-Min","year":"2007","unstructured":"Jeng-Min Chiou and Pai-Ling Li. 2007. Functional clustering and identifying substructures of longitudinal data. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 69, 4 (2007), 679\u2013699.","journal-title":"Journal of the Royal Statistical Society: Series B (Statistical Methodology)"},{"issue":"4","key":"e_1_3_1_16_2","doi-asserted-by":"crossref","first-page":"1523","DOI":"10.1109\/TIT.2005.844059","article-title":"Clustering by compression","volume":"51","author":"Cilibrasi Rudi","year":"2005","unstructured":"Rudi Cilibrasi and Paul M. B. Vit\u00e1nyi. 2005. Clustering by compression. IEEE Transactions on Information Theory 51, 4 (2005), 1523\u20131545.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"5","key":"e_1_3_1_17_2","doi-asserted-by":"crossref","first-page":"1830","DOI":"10.1137\/120865112","article-title":"Jaywalking your dog: Computing the Fr\u00e9chet distance with shortcuts","volume":"42","author":"Driemel Anne","year":"2013","unstructured":"Anne Driemel and Sariel Har-Peled. 2013. Jaywalking your dog: Computing the Fr\u00e9chet distance with shortcuts. SIAM Journal on Computing 42, 5 (2013), 1830\u20131866.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_1_18_2","first-page":"766","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Driemel Anne","year":"2016","unstructured":"Anne Driemel, Amer Krivosija, and Christian Sohler. 2016. Clustering time series under the Fr\u00e9chet distance. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms. 766\u2013785."},{"key":"e_1_3_1_19_2","first-page":"Article 28, 16","volume-title":"Proceedings of the 35th International Symposium on Computational Geometry","author":"Driemel Anne","year":"2019","unstructured":"Anne Driemel, Jeff M. Phillips, and Ioannis Psarros. 2019. The VC dimension of metric balls under Fr\u00e9chet and Hausdorff distances. In Proceedings of the 35th International Symposium on Computational Geometry. Article 28, 16 pages."},{"key":"e_1_3_1_20_2","first-page":"569","volume-title":"Proceedings of the 43rd ACM Symposium on Theory of Computing","author":"Feldman Dan","year":"2011","unstructured":"Dan Feldman and Michael Langberg. 2011. A unified framework for approximating and clustering data. In Proceedings of the 43rd ACM Symposium on Theory of Computing. ACM, New York, NY, 569\u2013578."},{"issue":"2","key":"e_1_3_1_21_2","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/s00357-005-0013-8","article-title":"A proposal for robust curve clustering","volume":"22","author":"Garcia-Escudero Luis Angel","year":"2005","unstructured":"Luis Angel Garcia-Escudero and Alfonso Gordaliza. 2005. A proposal for robust curve clustering. Journal of Classification 22, 2 (2005), 185\u2013201.","journal-title":"Journal of Classification"},{"key":"e_1_3_1_22_2","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/978-3-540-28608-0_8","volume-title":"Data Stream Management\u2014Processing High-Speed Data Streams","author":"Guha Sudipto","year":"2016","unstructured":"Sudipto Guha and Nina Mishra. 2016. Clustering data streams. In Data Stream Management\u2014Processing High-Speed Data Streams, Minos N. Garofalakis, Johannes Gehrke, and Rajeev Rastogi (Eds.). Springer, 169\u2013187."},{"key":"e_1_3_1_23_2","first-page":"291","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing","author":"Har-Peled Sariel","year":"2004","unstructured":"Sariel Har-Peled and Soham Mazumdar. 2004. On coresets for k-means and k-median clustering. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing. 291\u2013300."},{"key":"e_1_3_1_24_2","first-page":"814","volume-title":"Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science","author":"Huang Lingxiao","year":"2018","unstructured":"Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, and Xuan Wu. 2018. Epsilon-coresets for clustering (with outliers) in doubling metrics. In Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science. IEEE, Los Alamitos, CA, 814\u2013825."},{"key":"e_1_3_1_25_2","first-page":"71","article-title":"Polygonal approximations of a curve\u2013formulations and algorithms","volume":"6","author":"Imai Hiroshi","year":"1988","unstructured":"Hiroshi Imai and Masao Iri. 1988. Polygonal approximations of a curve\u2013formulations and algorithms. Machine Intelligence and Pattern Recognition 6 (Jan.1988), 71\u201386.","journal-title":"Machine Intelligence and Pattern Recognition"},{"key":"e_1_3_1_26_2","volume-title":"High-Dimensional Computational Geometry","author":"Indyk Piotr","year":"2000","unstructured":"Piotr Indyk. 2000. High-Dimensional Computational Geometry. Ph. D. Dissertation. Stanford University, Stanford, CA."},{"issue":"3","key":"e_1_3_1_27_2","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/BF02289588","article-title":"Hierarchical clustering schemes","volume":"32","author":"Johnson Stephen C.","year":"1967","unstructured":"Stephen C. Johnson. 1967. Hierarchical clustering schemes. Psychometrika 32, 3 (1967), 241\u2013254.","journal-title":"Psychometrika"},{"key":"e_1_3_1_28_2","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1109\/FOCS.2004.7","volume-title":"Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201904)","author":"Kumar Amit","year":"2004","unstructured":"Amit Kumar, Yogish Sabharwal, and Sandeep Sen. 2004. A simple linear time (1+ \\(\\varepsilon\\) )-approximation algorithm for k-means clustering in any dimensions. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201904). IEEE, Los Alamitos, CA, 454\u2013462."},{"key":"e_1_3_1_29_2","first-page":"12807","volume-title":"Advances in Neural Information Processing Systems 32","author":"Meintrup Stefan","year":"2019","unstructured":"Stefan Meintrup, Alexander Munteanu, and Dennis Rohde. 2019. Random projections and sampling algorithms for clustering of high-dimensional polygonal curves. In Advances in Neural Information Processing Systems 32. 12807\u201312817."},{"key":"e_1_3_1_30_2","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis (2nd ed.)","author":"Mitzenmacher Michael","year":"2017","unstructured":"Michael Mitzenmacher and Eli Upfal. 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis (2nd ed.). Cambridge University Press, Cambridge, MA."},{"key":"e_1_3_1_31_2","first-page":"Article 58, 15","volume-title":"Proceedings of the 36th International Symposium on Computational Geometry.","author":"Nath Abhinandan","year":"2020","unstructured":"Abhinandan Nath and Erin Taylor. 2020. k-Median clustering under discrete Fr\u00e9chet and Hausdorff distances. In Proceedings of the 36th International Symposium on Computational Geometry.Article 58, 15 pages."},{"issue":"1","key":"e_1_3_1_32_2","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/j.tcs.2011.09.029","article-title":"Summarizing a set of time series by averaging: From Steiner sequence to compact multiple alignment","volume":"414","author":"Petitjean Fran\u00e7ois","year":"2012","unstructured":"Fran\u00e7ois Petitjean and Pierre Gan\u00e7arski. 2012. Summarizing a set of time series by averaging: From Steiner sequence to compact multiple alignment. Theoretical Computer Science 414, 1 (2012), 76\u201391.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"e_1_3_1_33_2","doi-asserted-by":"crossref","first-page":"678","DOI":"10.1016\/j.patcog.2010.09.013","article-title":"A global averaging method for dynamic time warping, with applications to clustering","volume":"44","author":"Petitjean Fran\u00e7ois","year":"2011","unstructured":"Fran\u00e7ois Petitjean, Alain Ketterlin, and Pierre Gan\u00e7arski. 2011. A global averaging method for dynamic time warping, with applications to clustering. Pattern Recognition 44, 3 (2011), 678\u2013693.","journal-title":"Pattern Recognition"},{"issue":"1","key":"e_1_3_1_34_2","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","article-title":"Graph clustering","volume":"1","author":"Schaeffer Satu Elisa","year":"2007","unstructured":"Satu Elisa Schaeffer. 2007. Graph clustering. Computer Science Review 1, 1 (2007), 27\u201364.","journal-title":"Computer Science Review"},{"issue":"2","key":"e_1_3_1_35_2","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1109\/MSP.2010.939739","article-title":"Subspace clustering","volume":"28","author":"Vidal Ren\u00e9","year":"2011","unstructured":"Ren\u00e9 Vidal. 2011. Subspace clustering. IEEE Signal Processing Magazine 28, 2 (2011), 52\u201368.","journal-title":"IEEE Signal Processing Magazine"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3559764","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3559764","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:07:57Z","timestamp":1750183677000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3559764"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,31]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,31]]}},"alternative-id":["10.1145\/3559764"],"URL":"https:\/\/doi.org\/10.1145\/3559764","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,31]]},"assertion":[{"value":"2021-02-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}