{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T09:20:11Z","timestamp":1773220811870,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T00:00:00Z","timestamp":1773100800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T00:00:00Z","timestamp":1773100800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,4]]},"DOI":"10.1007\/s00453-025-01367-z","type":"journal-article","created":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T11:39:29Z","timestamp":1773142769000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Delaunay-Like Triangulation of Smooth Orientable Submanifolds by $$\\ell _1$$-Norm Minimization"],"prefix":"10.1007","volume":"88","author":[{"given":"Dominique","family":"Attali","sequence":"first","affiliation":[]},{"given":"Andr\u00e9","family":"Lieutier","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,3,10]]},"reference":[{"key":"1367_CR1","unstructured":"Attali, D., Lieutier, A.: Flat Delaunay complexes for homeomorphic manifold reconstruction (2022)"},{"key":"1367_CR2","doi-asserted-by":"crossref","unstructured":"Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., Stuetzle, W.: Surface reconstruction from unorganized points. In: Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH), pp. 71\u201378 (1992)","DOI":"10.1145\/133994.134011"},{"issue":"4","key":"1367_CR3","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/PL00009475","volume":"22","author":"N Amenta","year":"1999","unstructured":"Amenta, N., Bern, M.: Surface reconstruction by Voronoi filtering. Discret. Comput. Geom. 22(4), 481\u2013504 (1999)","journal-title":"Discret. Comput. Geom."},{"key":"1367_CR4","doi-asserted-by":"publisher","unstructured":"Amenta, N., Choi, S., Kolluri, R.K.: The power crust. In: Anderson, D.C., Lee, K. (eds.) Sixth ACM Symposium on Solid Modeling and Applications, pp. 249\u2013266. ACM, Sheraton Inn, Ann Arbor, Michigan, USA (2001). https:\/\/doi.org\/10.1145\/376957.376986","DOI":"10.1145\/376957.376986"},{"key":"1367_CR5","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H.: Surface reconstruction by wrapping finite sets in space. Discrete and computational geometry: the Goodman-Pollack Festschrift, 379\u2013404 (2003)","DOI":"10.1007\/978-3-642-55566-4_17"},{"key":"1367_CR6","doi-asserted-by":"crossref","unstructured":"Giesen, J., John, M.: Surface reconstruction based on a dynamical system. In: Computer Graphics Forum, vol. 21, pp. 363\u2013371 (2002). Wiley Online Library","DOI":"10.1111\/1467-8659.00596"},{"key":"1367_CR7","unstructured":"Cheng, S.-W., Dey, T.K., Ramos, E.A.: Manifold reconstruction from point samples. In: SODA, vol. 5, pp. 1018\u20131027 (2005)"},{"key":"1367_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546860","volume-title":"Curve and Surface Reconstruction: Algorithms with Mathematical Analysis","author":"TK Dey","year":"2006","unstructured":"Dey, T.K.: Curve and Surface Reconstruction: Algorithms with Mathematical Analysis. Cambridge University Press, New York, USA (2006)"},{"key":"1367_CR9","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"15","volume-title":"40th International Symposium on Computational Geometry (SoCG 2024)","author":"U Bauer","year":"2024","unstructured":"Bauer, U., Roll, F.: Wrapping cycles in delaunay complexes: Bridging persistent homology and discrete morse theory. In: Mulzer, W., Phillips, J.M. (eds.) 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), vol. 293, pp. 15\u201311516. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2024)"},{"key":"1367_CR10","unstructured":"Chen, L., Xu, J.-c.: Optimal delaunay triangulations. J. Comput. Math. 299\u2013308 (2004)"},{"issue":"3","key":"1367_CR11","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1145\/1073204.1073238","volume":"24","author":"P Alliez","year":"2005","unstructured":"Alliez, P., Cohen-Steiner, D., Yvinec, M., Desbrun, M.: Variational tetrahedral meshing. ACM Trans. Gr. TOG 24(3), 617\u2013625 (2005)","journal-title":"ACM Trans. Gr. TOG"},{"issue":"9","key":"1367_CR12","doi-asserted-by":"publisher","first-page":"967","DOI":"10.1016\/j.cma.2010.11.007","volume":"200","author":"L Chen","year":"2011","unstructured":"Chen, L., Holst, M.: Efficient mesh optimization schemes based on optimal delaunay triangulations. Comput. Methods Appl. Mech. Eng. 200(9), 967\u2013984 (2011)","journal-title":"Comput. Methods Appl. Mech. Eng."},{"issue":"3","key":"1367_CR13","doi-asserted-by":"publisher","first-page":"930","DOI":"10.1137\/120875132","volume":"36","author":"Z Chen","year":"2014","unstructured":"Chen, Z., Wang, W., L\u00e9vy, B., Liu, L., Sun, F.: Revisiting optimal delaunay triangulation for 3d graded mesh generation. SIAM J. Sci. Comput. 36(3), 930\u2013954 (2014)","journal-title":"SIAM J. Sci. Comput."},{"key":"1367_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-804489-6.50001-X","volume-title":"Geometric Measure Theory: a Beginner\u2019s Guide","author":"F Morgan","year":"2016","unstructured":"Morgan, F.: Geometric Measure Theory: a Beginner\u2019s Guide. Academic press, Cambridge, Massachussets, United States (2016)"},{"issue":"1","key":"1367_CR15","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/s00454-013-9557-2","volume":"51","author":"J-D Boissonnat","year":"2014","unstructured":"Boissonnat, J.-D., Ghosh, A.: Manifold reconstruction using tangential delaunay complexes. Discret. Comput. Geom. 51(1), 221\u2013267 (2014)","journal-title":"Discret. Comput. Geom."},{"key":"1367_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/9781108297806","volume-title":"Geometric and topological inference","author":"J-D Boissonnat","year":"2018","unstructured":"Boissonnat, J.-D., Chazal, F., Yvinec, M.: Geometric and topological inference, vol. 57. Cambridge University Press, Cambridge, United Kingdom (2018)"},{"issue":"3","key":"1367_CR17","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s00454-010-9322-8","volume":"45","author":"C Chen","year":"2011","unstructured":"Chen, C., Freedman, D.: Hardness results for homology localization. Discret. Comput. Geom. 45(3), 425\u2013448 (2011). https:\/\/doi.org\/10.1007\/s00454-010-9322-8","journal-title":"Discret. Comput. Geom."},{"key":"1367_CR18","doi-asserted-by":"publisher","unstructured":"Borradaile, G., Maxwell, W., Nayyeri, A.: Minimum bounded chains and minimum homologous chains in embedded simplicial complexes. In: Cabello, S., Chen, D.Z. (eds.) 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 164, pp. 21\u201312115. Schloss Dagstuhl\u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2020). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2020.21","DOI":"10.4230\/LIPIcs.SoCG.2020.21"},{"issue":"4","key":"1367_CR19","doi-asserted-by":"publisher","first-page":"1026","DOI":"10.1137\/100800245","volume":"40","author":"TK Dey","year":"2011","unstructured":"Dey, T.K., Hirani, A.N., Krishnamoorthy, B.: Optimal homologous cycles, total unimodularity, and linear programming. SIAM J. Comput. 40(4), 1026\u20131044 (2011). https:\/\/doi.org\/10.1137\/100800245","journal-title":"SIAM J. Comput."},{"key":"1367_CR20","doi-asserted-by":"publisher","unstructured":"Chambers, E.W., Erickson, J., Nayyeri, A.: Minimum cuts and shortest homologous cycles. In: Proceedings of the 25th Annual Symposium on Computational Geometry - SCG \u201909, p. 377. ACM Press, Aarhus, Denmark (2009). https:\/\/doi.org\/10.1145\/1542362.1542426","DOI":"10.1145\/1542362.1542426"},{"key":"1367_CR21","doi-asserted-by":"crossref","unstructured":"Dey, T.K., Hou, T., Mandal, S.: Computing minimal persistent cycles: Polynomial and hard cases. In: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms. SODA\u201920, pp. 2587\u20132606. Society for Industrial and Applied Mathematics, USA (2020)","DOI":"10.1137\/1.9781611975994.158"},{"issue":"1","key":"1367_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00454-023-00485-1","volume":"70","author":"D Cohen-Steiner","year":"2023","unstructured":"Cohen-Steiner, D., Lieutier, A., Vuillamy, J.: Delaunay and regular triangulations as lexicographic optimal chains. Discret. Comput. Geom. 70(1), 1\u201350 (2023)","journal-title":"Discret. Comput. Geom."},{"issue":"4","key":"1367_CR23","doi-asserted-by":"publisher","first-page":"1155","DOI":"10.1007\/s00454-022-00432-6","volume":"68","author":"D Cohen-Steiner","year":"2022","unstructured":"Cohen-Steiner, D., Lieutier, A., Vuillamy, J.: Lexicographic optimal homologous chains and applications to point cloud triangulations. Discret. Comput. Geom. 68(4), 1155\u20131174 (2022)","journal-title":"Discret. Comput. Geom."},{"key":"1367_CR24","doi-asserted-by":"publisher","unstructured":"Jordan, C.: Essai sur la g\u00e9om\u00e9trie \u00e0 $$n$$ dimensions. Bulletin de la Soci\u00e9t\u00e9 Math\u00e9matique de France 3, 103\u2013174 (1875) https:\/\/doi.org\/10.24033\/bsmf.90","DOI":"10.24033\/bsmf.90"},{"key":"1367_CR25","volume-title":"Elements of algebraic topology","author":"JR Munkres","year":"1993","unstructured":"Munkres, J.R.: Elements of algebraic topology. Addison-Wesley Publishing Company Inc, MA, USA (1993)"},{"key":"1367_CR26","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139172998","volume-title":"Algorithmic geometry","author":"J-D Boissonnat","year":"1998","unstructured":"Boissonnat, J.-D., Yvinec, M.: Algorithmic geometry. Cambridge University Press, Cambridge, United Kingdom (1998)"},{"issue":"6","key":"1367_CR27","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1016\/0167-8396(90)90011-F","volume":"7","author":"S Rippa","year":"1990","unstructured":"Rippa, S.: Minimal roughness property of the delaunay triangulation. Comput. Aided Geom. Des.7(6), 489\u2013497 (1990)","journal-title":"Comput. Aided Geom. Des."},{"key":"1367_CR28","doi-asserted-by":"crossref","unstructured":"Musin, O.R.: Properties of the delaunay triangulation. In: Proceedings of the Thirteenth Annual Symposium on Computational Geometry, pp. 424\u2013426 (1997)","DOI":"10.1145\/262839.263061"},{"key":"1367_CR29","unstructured":"Chen, L.: Mesh smoothing schemes based on optimal delaunay triangulations. In: Proceedings of the 13th International Meshing Roundtable, IMR 2004, Williamsburg, Virginia, USA, September 19-22, 2004, pp. 109\u2013120 (2004). http:\/\/imr.sandia.gov\/papers\/abstracts\/Ch317.html"},{"issue":"3","key":"1367_CR30","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/BF01975867","volume":"15","author":"H Edelsbrunner","year":"1996","unstructured":"Edelsbrunner, H., Shah, N.R.: Incremental topological flipping works for regular triangulations. Algorithmica 15(3), 223\u2013241 (1996)","journal-title":"Algorithmica"},{"key":"1367_CR31","doi-asserted-by":"crossref","unstructured":"Zeller, S., Thaler, M.: Almost sure escape from the unit interval under the logistic map. American Mathematical Monthly, 155\u2013158 (2001)","DOI":"10.1080\/00029890.2001.11919736"},{"key":"1367_CR32","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1090\/S0002-9947-1959-0110078-1","volume":"93","author":"H Federer","year":"1959","unstructured":"Federer, H.: Curvature measures. Trans. Amer. Math. Soc 93, 418\u2013491 (1959)","journal-title":"Trans. Amer. Math. Soc"},{"key":"1367_CR33","unstructured":"Attali, D., Lieutier, A.: Delaunay-like triangulation of smooth orientable submanifolds by $$\\ell _1$$-norm minimization (2022). https:\/\/arxiv.org\/abs\/2203.06008"},{"key":"1367_CR34","doi-asserted-by":"publisher","unstructured":"Boissonnat, J.-D., Dyer, R., Ghosh, A.: The stability of delaunay triangulations. Int. J. Comput. Geom. Appl. 23(04n05), 303\u2013333 (2013) https:\/\/doi.org\/10.1142\/s0218195913600078","DOI":"10.1142\/s0218195913600078"},{"issue":"2","key":"1367_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1667053.1667060","volume":"57","author":"RA Moser","year":"2010","unstructured":"Moser, R.A., Tardos, G.: A constructive proof of the general lov\u00e1sz local lemma. J. ACM (JACM) 57(2), 1\u201315 (2010)","journal-title":"J. ACM (JACM)"},{"key":"1367_CR36","doi-asserted-by":"crossref","unstructured":"Attali, D., Lieutier, A.: Reconstructing shapes with guarantees by unions of convex sets. In: Proc. 26th Ann. Sympos. Comput. Geom., Snowbird, Utah, pp. 344\u2013353 (2010)","DOI":"10.1145\/1810959.1811015"},{"key":"1367_CR37","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/j.comgeo.2007.07.001","volume":"40","author":"F Chazal","year":"2008","unstructured":"Chazal, F., Lieutier, A.: Smooth manifold reconstruction from noisy and non uniform approximation with guarantees. Comput. Geom. Theo. Appl. 40, 156\u2013170 (2008)","journal-title":"Comput. Geom. Theo. Appl."},{"issue":"3","key":"1367_CR38","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00454-009-9144-8","volume":"41","author":"F Chazal","year":"2009","unstructured":"Chazal, F., Cohen-Steiner, D., Lieutier, A.: A sampling theory for compact sets in euclidean space. Discret. Comput. Geom. 41(3), 461\u2013479 (2009)","journal-title":"Discret. Comput. Geom."},{"issue":"4","key":"1367_CR39","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/j.comgeo.2012.02.009","volume":"46","author":"D Attali","year":"2013","unstructured":"Attali, D., Lieutier, A., Salinas, D.: Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes. Comput. Geom. Theo. Appl. 46(4), 448\u2013465 (2013)","journal-title":"Comput. Geom. Theo. Appl."},{"issue":"1\u20133","key":"1367_CR40","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/s00454-008-9053-2","volume":"39","author":"P Niyogi","year":"2008","unstructured":"Niyogi, P., Smale, S., Weinberger, S.: Finding the homology of submanifolds with high confidence from random samples. Discret. Comput. Geom. 39(1\u20133), 419\u2013441 (2008)","journal-title":"Discret. Comput. Geom."},{"key":"1367_CR41","unstructured":"Kim, J., Shin, J., Chazal, F., Rinaldo, A., Wasserman, L.: Homotopy reconstruction via the cech complex and the vietoris-rips complex. arXiv preprint arXiv:1903.06955 (2019)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01367-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01367-z","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01367-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T11:39:35Z","timestamp":1773142775000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01367-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,10]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["1367"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01367-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,10]]},"assertion":[{"value":"14 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 March 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"28"}}