{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T10:51:33Z","timestamp":1753181493888,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,7,12]],"date-time":"2019-07-12T00:00:00Z","timestamp":1562889600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EXC-2046\/1"],"award-info":[{"award-number":["EXC-2046\/1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2019,8,31]]},"abstract":"<jats:p>We introduce the notion of harmonic triangulations: a harmonic triangulation simultaneously minimizes the Dirichlet energy of all piecewise linear functions. By a famous result of Rippa, Delaunay triangulations are the harmonic triangulations of planar point sets. We prove by explicit counterexample that in 3D a harmonic triangulation does not exist in general. However, we show that bistellar flips are harmonic: if they decrease Dirichlet energy for one set of function values, they do so for all. This observation gives rise to the notion of locally harmonic triangulations. We demonstrate that locally harmonic triangulations can be efficiently computed, and efficiently reduce sliver tetrahedra. The notion of harmonic triangulation also gives rise to a scalar measure of the quality of a triangulation, which can be used to prioritize flips and optimize the position of vertices. Tetrahedral meshes generated by optimizing this function generally show better quality than Delaunay-based optimization techniques.<\/jats:p>","DOI":"10.1145\/3306346.3322986","type":"journal-article","created":{"date-parts":[[2019,7,12]],"date-time":"2019-07-12T19:04:08Z","timestamp":1562958248000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Harmonic triangulations"],"prefix":"10.1145","volume":"38","author":[{"given":"Marc","family":"Alexa","sequence":"first","affiliation":[{"name":"TU Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2019,7,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964997"},{"volume-title":"Convex polyhedra","author":"Alexandrov Aleksandr D","key":"e_1_2_2_2_1","unstructured":"Aleksandr D Alexandrov . 2005. Convex polyhedra . Springer , Berlin, Heidelberg . Aleksandr D Alexandrov. 2005. Convex polyhedra. Springer, Berlin, Heidelberg."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073238"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216006"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0713021"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142994265292"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/313651.313694"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1341391.1341394"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1098\/rstl.1869.0010"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings, 13th International Meshing Roundtable. Sandia National Laboratories","author":"Chen Long","year":"2004","unstructured":"Long Chen . 2004 . Mesh Smoothing Schemes Based on Optimal Delaunay Triangulations .. In Proceedings, 13th International Meshing Roundtable. Sandia National Laboratories , Williamburg, VA, USA, 109--120. Long Chen. 2004. Mesh Smoothing Schemes Based on Optimal Delaunay Triangulations.. In Proceedings, 13th International Meshing Roundtable. Sandia National Laboratories, Williamburg, VA, USA, 109--120."},{"key":"e_1_2_2_11_1","first-page":"299","article-title":"Optimal Delaunay Triangulations","volume":"22","author":"Chen Long","year":"2004","unstructured":"Long Chen and Jinchao Xu . 2004 . Optimal Delaunay Triangulations . Journal of Computational Mathematics 22 , 2 (2004), 299 -- 308 . Long Chen and Jinchao Xu. 2004. Optimal Delaunay Triangulations. Journal of Computational Mathematics 22, 2 (2004), 299--308.","journal-title":"Journal of Computational Mathematics"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2010.02.002"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/120875132"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/355483.355487"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2602143"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12971-1"},{"key":"e_1_2_2_17_1","first-page":"793","article-title":"Distributed and lumped networks","volume":"8","author":"Duffin Richard J","year":"1959","unstructured":"Richard J Duffin . 1959 . Distributed and lumped networks . Journal of Mathematics and Mechanics 8 , 5 (1959), 793 -- 826 . Richard J Duffin. 1959. Distributed and lumped networks. Journal of Mathematics and Mechanics 8, 5 (1959), 793--826.","journal-title":"Journal of Mathematics and Mechanics"},{"volume-title":"Partial Differential Equations and Calculus of Variations","author":"Dziuk Gerhard","key":"e_1_2_2_18_1","unstructured":"Gerhard Dziuk . 1988. Finite Elements for the Beltrami operator on arbitrary surfaces . In Partial Differential Equations and Calculus of Variations , Stefan Hildebrandt and Rolf Leis (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg , 142--155. Gerhard Dziuk. 1988. Finite Elements for the Beltrami operator on arbitrary surfaces. In Partial Differential Equations and Calculus of Variations, Stefan Hildebrandt and Rolf Leis (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 142--155."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/142675.142688"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201358"},{"key":"e_1_2_2_21_1","unstructured":"Jean Gallier and Jocelyn Quaintance. 2017. Aspects of Convex Geometry Polyhedra Linear Programming Shellings Voronoi Diagrams Delaunay Triangulations. Book in progress earlier version available as arXiv:0805.0292.  Jean Gallier and Jocelyn Quaintance. 2017. Aspects of Convex Geometry Polyhedra Linear Programming Shellings Voronoi Diagrams Delaunay Triangulations. Book in progress earlier version available as arXiv:0805.0292."},{"key":"e_1_2_2_22_1","unstructured":"Ga\u00ebl Guennebaud Beno\u00eet Jacob etal 2010. Eigen v3. http:\/\/eigen.tuxfamily.org.  Ga\u00ebl Guennebaud Beno\u00eet Jacob et al. 2010. Eigen v3. http:\/\/eigen.tuxfamily.org."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201353"},{"key":"e_1_2_2_24_1","unstructured":"Cl\u00e9ment Jamin Sylvain Pion and Monique Teillaud. 2018. 3D Triangulations. In CGAL User and Reference Manual (4.13 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/4.13\/Manual\/packages.html#PkgTriangulation3Summary  Cl\u00e9ment Jamin Sylvain Pion and Monique Teillaud. 2018. 3D Triangulations. In CGAL User and Reference Manual (4.13 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/4.13\/Manual\/packages.html#PkgTriangulation3Summary"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0910044"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0729031"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276448"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(72)90093-3"},{"key":"e_1_2_2_29_1","volume-title":"Barr","author":"Meyer Mark","year":"2003","unstructured":"Mark Meyer , Mathieu Desbrun , Peter Schr\u00f6der , and Alan H . Barr . 2003 . Discrete Differential-Geometry Operators for Triangulated 2-Manifolds. In Visualization and Mathematics III, Hans-Christian Hege and Konrad Polthier (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg, 35--57. Mark Meyer, Mathieu Desbrun, Peter Schr\u00f6der, and Alan H. Barr. 2003. Discrete Differential-Geometry Operators for Triangulated 2-Manifolds. In Visualization and Mathematics III, Hans-Christian Hege and Konrad Polthier (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 35--57."},{"key":"e_1_2_2_30_1","volume-title":"Proceedings, 12th International Meshing Roundtable. Sandia National Laboratories","author":"Molino Neil","year":"2003","unstructured":"Neil Molino , Robert Bridson , Joseph Teran , and Ronald Fedkiw . 2003 . A crystalline, red green strategy for meshing highly deformable objects with tetrahedra . In Proceedings, 12th International Meshing Roundtable. Sandia National Laboratories , Santa Fe, NM, USA, 103--114. Neil Molino, Robert Bridson, Joseph Teran, and Ronald Fedkiw. 2003. A crystalline, red green strategy for meshing highly deformable objects with tetrahedra. In Proceedings, 12th International Meshing Roundtable. Sandia National Laboratories, Santa Fe, NM, USA, 103--114."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/262839.263061"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.1993.10504266"},{"key":"e_1_2_2_33_1","volume-title":"Flannery","author":"Press William H.","year":"1992","unstructured":"William H. Press , Saul A. Teukolsky , William T. Vetterling , and Brian P . Flannery . 1992 . Numerical Recipes in C : The Art of Scientific Computing (second ed.). Cambridge University Press . William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. 1992. Numerical Recipes in C: The Art of Scientific Computing (second ed.). Cambridge University Press."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(90)90011-F"},{"key":"e_1_2_2_35_1","unstructured":"Jonathan Shewchuk. 2002a. What is a good linear finite element? interpolation conditioning anisotropy and quality measures (preprint). https:\/\/people.eecs.berkeley.edu\/~jrs\/papers\/elemj.pdf  Jonathan Shewchuk. 2002a. What is a good linear finite element? interpolation conditioning anisotropy and quality measures (preprint). https:\/\/people.eecs.berkeley.edu\/~jrs\/papers\/elemj.pdf"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00047-5"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/21.3.243"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531381"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1281991.1281995"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-99-01148-5"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3306346.3322986","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3306346.3322986","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:44Z","timestamp":1750206344000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3306346.3322986"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,12]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,8,31]]}},"alternative-id":["10.1145\/3306346.3322986"],"URL":"https:\/\/doi.org\/10.1145\/3306346.3322986","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2019,7,12]]},"assertion":[{"value":"2019-07-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}