{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T17:11:35Z","timestamp":1768410695090,"version":"3.49.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T00:00:00Z","timestamp":1644364800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T00:00:00Z","timestamp":1644364800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"NWO","award":["project no. 024.002.003"],"award-info":[{"award-number":["project no. 024.002.003"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1007\/s00453-022-00929-9","type":"journal-article","created":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T08:02:58Z","timestamp":1644393778000},"page":"1467-1489","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Preclustering Algorithms for Imprecise Points"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8345-8783","authenticated-orcid":false,"given":"Mohammad Ali","family":"Abam","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5770-3784","authenticated-orcid":false,"given":"Mark","family":"de Berg","sequence":"additional","affiliation":[]},{"given":"Sina","family":"Farahzad","sequence":"additional","affiliation":[]},{"given":"Mir Omid","family":"Haji Mirsadeghi","sequence":"additional","affiliation":[]},{"given":"Morteza","family":"Saghafian","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,9]]},"reference":[{"issue":"2","key":"929_CR1","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s00453-001-0110-y","volume":"33","author":"PK Agarwal","year":"2002","unstructured":"Agarwal, P.K., Procopiuc, C.M.: Exact and approximation algorithms for clustering. Algorithmica 33(2), 201\u2013226 (2002). https:\/\/doi.org\/10.1007\/s00453-001-0110-y","journal-title":"Algorithmica"},{"key":"929_CR2","doi-asserted-by":"publisher","unstructured":"Arora, S., Raghavan, P., Rao, S.: Approximation schemes for euclidean k-medians and related problems. In: Proceedings of the ACM Symposium on the Theory of Computing, pp. 106\u2013113 (1998). https:\/\/doi.org\/10.1145\/276698.276718","DOI":"10.1145\/276698.276718"},{"issue":"5","key":"929_CR3","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1017\/S0963548312000193","volume":"21","author":"Y Bilu","year":"2012","unstructured":"Bilu, Y., Linial, N.: Are stable instances easy? Comb. Probab. Comput. 21(5), 643\u2013660 (2012). https:\/\/doi.org\/10.1017\/S0963548312000193","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"929_CR4","doi-asserted-by":"publisher","first-page":"674","DOI":"10.1007\/s00453-010-9430-0","volume":"61","author":"K Buchin","year":"2011","unstructured":"Buchin, K., L\u00f6ffler, M., Morin, P., Mulzer, W.: Preprocessing imprecise points for delaunay triangulation: simplified and extended. Algorithmica 61(3), 674\u2013693 (2011). https:\/\/doi.org\/10.1007\/s00453-010-9430-0","journal-title":"Algorithmica"},{"key":"929_CR5","doi-asserted-by":"publisher","unstructured":"Cohen-Addad, V., Schwiegelshohn, C.: On the local structure of stable clustering instances. In: C. Umans (ed.) 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15\u201317, 2017, pp. 49\u201360. IEEE Computer Society (2017). https:\/\/doi.org\/10.1109\/FOCS.2017.14","DOI":"10.1109\/FOCS.2017.14"},{"key":"929_CR6","doi-asserted-by":"publisher","unstructured":"Feldman, D., Monemizadeh, M., Sohler, C.: A PTAS for k-means clustering based on weak coresets. In: Proceedings of ACM Symposium on Computational Geometry, pp. 11\u201318 (2007). https:\/\/doi.org\/10.1145\/1247069.1247072","DOI":"10.1145\/1247069.1247072"},{"key":"929_CR7","doi-asserted-by":"publisher","unstructured":"Gullo, F., Tagarelli, A.: Uncertain centroid based partitional clustering of uncertain data. Proc. VLDB Endow. 5(7), 610\u2013621 (2012). https:\/\/doi.org\/10.14778\/2180912.2180914","DOI":"10.14778\/2180912.2180914"},{"issue":"2","key":"929_CR8","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the k-center problem. Math. Oper. Res. 10(2), 180\u2013184 (1985). https:\/\/doi.org\/10.1287\/moor.10.2.180","journal-title":"Math. Oper. Res."},{"key":"929_CR9","doi-asserted-by":"publisher","unstructured":"Jaiswal, R., Kumar, A., Sen, S.: A simple D 2-sampling based PTAS for k-means and other clustering problems. In: Computing and Combinatorics COCOON 2012. Lecture Notes in Computer Science, vol. 7434, pp. 13\u201324. Springer (2012). https:\/\/doi.org\/10.1007\/978-3-642-32241-9_2","DOI":"10.1007\/978-3-642-32241-9_2"},{"issue":"4","key":"929_CR10","doi-asserted-by":"publisher","first-page":"832","DOI":"10.1007\/s10878-012-9488-5","volume":"26","author":"W Ju","year":"2013","unstructured":"Ju, W., Luo, J., Zhu, B., Daescu, O.: Largest area convex hull of imprecise data based on axis-aligned squares. J. Comb. Optim. 26(4), 832\u2013859 (2013). https:\/\/doi.org\/10.1007\/s10878-012-9488-5","journal-title":"J. Comb. Optim."},{"key":"929_CR11","doi-asserted-by":"publisher","unstructured":"Kao, B., Lee, S.D., Cheung, D.W., Ho, W., Chan, K.F.: Clustering uncertain data using voronoi diagrams. In: Proceedings of the 8th IEEE International Conference on Data Mining (ICDM 2008), December 15\u201319, 2008, Pisa, Italy, pp. 333\u2013342. IEEE Computer Society (2008). https:\/\/doi.org\/10.1109\/ICDM.2008.31","DOI":"10.1109\/ICDM.2008.31"},{"key":"929_CR12","doi-asserted-by":"publisher","unstructured":"Kolliopoulos, S.G., Rao, S.: A nearly linear-time approximation scheme for the euclidean kappa-median problem. In: Algorithms\u2014ESA Proceedings. Lecture Notes in Computer Science, vol. 1643, pp. 378\u2013389. Springer (1999). https:\/\/doi.org\/10.1007\/3-540-48481-7_33","DOI":"10.1007\/3-540-48481-7_33"},{"issue":"2","key":"929_CR13","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1007\/s00453-017-0292-6","volume":"80","author":"C Liu","year":"2018","unstructured":"Liu, C., Montanari, S.: Minimizing the diameter of a spanning tree for imprecise points. Algorithmica 80(2), 801\u2013826 (2018). https:\/\/doi.org\/10.1007\/s00453-017-0292-6","journal-title":"Algorithmica"},{"key":"929_CR14","unstructured":"L\u00f6ffler, M.: Data imprecision in computational geometry. Ph.D. thesis, Utrecht University, Netherlands (2009)"},{"issue":"2","key":"929_CR15","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00453-008-9174-2","volume":"56","author":"M L\u00f6ffler","year":"2010","unstructured":"L\u00f6ffler, M., van Kreveld, M.J.: Largest and smallest convex hulls for imprecise points. Algorithmica 56(2), 235\u2013269 (2010). https:\/\/doi.org\/10.1007\/s00453-008-9174-2","journal-title":"Algorithmica"},{"key":"929_CR16","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.R.: The planar k-means problem is nphard. Theor. Comput. Sci. 442, 13\u201321 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2010.05.034","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"929_CR17","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1137\/0213014","volume":"13","author":"N Megiddo","year":"1984","unstructured":"Megiddo, N., Supowit, K.J.: On the complexity of some common geometric location problems. SIAM J. Comput. 13(1), 182\u2013196 (1984). https:\/\/doi.org\/10.1137\/0213014","journal-title":"SIAM J. Comput."},{"key":"929_CR18","doi-asserted-by":"publisher","unstructured":"Nagai, T., Tokura, N.: Tight error bounds of geometric problems on convex objects with imprecise coordinates. In: JCDCG. Lecture Notes in Computer Science, vol. 2098, pp. 252\u2013263. Springer (2000). https:\/\/doi.org\/10.1007\/3-540-47738-1_24","DOI":"10.1007\/3-540-47738-1_24"},{"key":"929_CR19","doi-asserted-by":"publisher","unstructured":"Saulpic, D., Cohen-Addad, V., Feldmann, A.E.: Near-linear time approximations schemes for clustering in doubling metrics. In: D. Zuckerman (ed.) 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9\u201312, 2019, pp. 540\u2013559. IEEE Computer Society (2019). https:\/\/doi.org\/10.1109\/FOCS.2019.00041","DOI":"10.1109\/FOCS.2019.00041"},{"key":"929_CR20","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.comgeo.2016.10.001","volume":"61","author":"F Sheikhi","year":"2017","unstructured":"Sheikhi, F., Mohades, A., de Berg, M., Mehrabi, A.D.: Separability of imprecise points. Comput. Geom. 61, 24\u201337 (2017). https:\/\/doi.org\/10.1016\/j.comgeo.2016.10.001","journal-title":"Comput. Geom."},{"key":"929_CR21","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"DB Shmoys","year":"1993","unstructured":"Shmoys, D.B., Tardos, \u00c9.: An approximation algorithm for the generalized assignment problem. Math. Program. 62, 461\u2013474 (1993). https:\/\/doi.org\/10.1007\/BF01585178","journal-title":"Math. Program."},{"issue":"10","key":"929_CR22","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/1562764.1562785","volume":"52","author":"DA Spielman","year":"2009","unstructured":"Spielman, D.A., Teng, S.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52(10), 76\u201384 (2009). https:\/\/doi.org\/10.1145\/1562764.1562785","journal-title":"Commun. ACM"},{"issue":"3","key":"929_CR23","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/PL00009362","volume":"19","author":"I Talata","year":"1998","unstructured":"Talata, I.: Exponential lower bound for the translative kissing numbers of d-dimensional convex bodies. Discrete Comput. Geom. 19(3), 447\u2013455 (1998). https:\/\/doi.org\/10.1007\/PL00009362","journal-title":"Discrete Comput. Geom."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00929-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00929-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00929-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,28]],"date-time":"2022-05-28T08:34:16Z","timestamp":1653726856000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00929-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,9]]},"references-count":23,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["929"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00929-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,9]]},"assertion":[{"value":"20 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}