{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T01:22:49Z","timestamp":1775870569153,"version":"3.50.1"},"reference-count":68,"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\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1835712 1821334 1652515"],"award-info":[{"award-number":["1835712 1821334 1652515"]}],"id":[{"id":"10.13039\/100000001","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>Tutte embedding is one of the most common building blocks in geometry processing algorithms due to its simplicity and provable guarantees. Although provably correct in infinite precision arithmetic, it fails in challenging cases when implemented using floating point arithmetic, largely due to the induced exponential area changes.<\/jats:p>\n          <jats:p>\n            We propose\n            <jats:italic>Progressive Embedding<\/jats:italic>\n            , with similar theoretical guarantees to Tutte embedding, but more resilient to the rounding error of floating point arithmetic. Inspired by progressive meshes, we collapse edges on an invalid embedding to a valid, simplified mesh, then insert points back while maintaining validity. We demonstrate the robustness of our method by computing embeddings for a large collection of disk topology meshes.\n          <\/jats:p>\n          <jats:p>By combining our robust embedding with a variant of the matchmaker algorithm, we propose a general algorithm for the problem of mapping multiply connected domains with arbitrary hard constraints to the plane, with applications in texture mapping and remeshing.<\/jats:p>","DOI":"10.1145\/3306346.3323012","type":"journal-article","created":{"date-parts":[[2019,7,12]],"date-time":"2019-07-12T19:04:08Z","timestamp":1562958248000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":42,"title":["Progressive embedding"],"prefix":"10.1145","volume":"38","author":[{"given":"Hanxiao","family":"Shen","sequence":"first","affiliation":[{"name":"New York University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhongshi","family":"Jiang","sequence":"additional","affiliation":[{"name":"New York University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Denis","family":"Zorin","sequence":"additional","affiliation":[{"name":"New York University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniele","family":"Panozzo","sequence":"additional","affiliation":[{"name":"New York University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,7,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073615"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818099"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2982412"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601158"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766921"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2462014"},{"key":"e_1_2_2_7_1","volume-title":"M. Tarini, and D. Zorin.","author":"Bommes D.","year":"2012"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531383"},{"key":"e_1_2_2_9_1","unstructured":"Herv\u00e9 Br\u00f6nnimann Andreas Fabri Geert-Jan Giezeman Susan Hert Michael Hoffmann Lutz Kettner Sylvain Pion and Stefan Schirra. 2018. 2D and 3D Linear Geometry Kernel. In CGAL User and Reference Manual (4.13 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/4.13\/Manual\/packages.html#PkgKernel23Summary  Herv\u00e9 Br\u00f6nnimann Andreas Fabri Geert-Jan Giezeman Susan Hert Michael Hoffmann Lutz Kettner Sylvain Pion and Stefan Schirra. 2018. 2D and 3D Linear Geometry Kernel. In CGAL User and Reference Manual (4.13 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/4.13\/Manual\/packages.html#PkgKernel23Summary"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925890"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1964371.1964384"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13243"},{"key":"e_1_2_2_13_1","volume-title":"Proceedings of the 12th International Meshing Roundtable. 201--213","author":"Degener P."},{"key":"e_1_2_2_14_1","first-page":"23","article-title":"Topology preserving edge contraction","volume":"66","author":"Dey Tamal K","year":"1999","journal-title":"Publ. Inst. Math.(Beograd)(NS)"},{"key":"e_1_2_2_15_1","first-page":"229","article-title":"On straight line representation of planar graphs","volume":"11","author":"F\u00e1ry Istv\u00e1n","year":"1948","journal-title":"Acta Univ. Szeged. Sect. Sci. Math."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8396(96)00031-3"},{"key":"e_1_2_2_17_1","volume-title":"Floater and Kai Hormann","author":"Michael","year":"2005"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236463.1236468"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2980231"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766938"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-8493(00)00108-4"},{"key":"e_1_2_2_22_1","volume-title":"GNU MP: The GNU Multiple Precision Arithmetic Library (5.0.5 ed.)","author":"Granlund Torbj\u00f6rn","year":"2018"},{"key":"e_1_2_2_23_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_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00064-5"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/237170.237216"},{"key":"e_1_2_2_26_1","first-page":"153","article-title":"MIPS: An Efficient Global Parametrization Method","volume":"1999","author":"Hormann K.","year":"2000","journal-title":"Curve and Surface Design: Saint-Malo"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508044.1508091"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201353"},{"key":"e_1_2_2_29_1","volume-title":"Piecewise linear topology","author":"Hudson John FP"},{"key":"e_1_2_2_30_1","doi-asserted-by":"crossref","unstructured":"Alec Jacobson Daniele Panozzo etal 2016. libigl: A simple C++ geometry processing library. http:\/\/libigl.github.io\/libigl\/.  Alec Jacobson Daniele Panozzo et al. 2016. libigl: A simple C++ geometry processing library. http:\/\/libigl.github.io\/libigl\/.","DOI":"10.1145\/3134472.3134497"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3130800.3130895"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818098"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925920"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015811"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882271"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90040-6"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/795680.797444"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2007.70432"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566590"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275042"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185604"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/130939754"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201331"},{"key":"e_1_2_2_44_1","volume-title":"Simplifying triangulations of S<sup>3<\/sup>. Pacific journal of mathematics 208, 2","author":"Mijatovi\u0107 Aleksandar","year":"2003"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766907"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601154"},{"key":"e_1_2_2_47_1","unstructured":"Eli Packer. 2018. 2D Snap Rounding. In CGAL User and Reference Manual (4.13 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/4.13\/Manual\/packages.html#PkgSnapRounding2Summary  Eli Packer. 2018. 2D Snap Rounding. In CGAL User and Reference Manual (4.13 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/4.13\/Manual\/packages.html#PkgSnapRounding2Summary"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201290"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601123"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3130800.3130845"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383277"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983621"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383307"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/320176.320191"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015812"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12179"},{"key":"e_1_2_2_57_1","volume-title":"Proceedings of the ACM SIGGRAPH\/Eurographics symposium on computer animation. Eurographics Association, 85--95","author":"Segall Aviv","year":"2016"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1561\/0600000011"},{"key":"e_1_2_2_59_1","volume-title":"Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. In Applied Computational Geometry: Towards Geometric Engineering, Ming C","author":"Shewchuk Jonathan Richard","year":"1996"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(92)90019-O"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073618"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766947"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/602099.602154"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-13.1.743"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601227"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1037957.1037958"},{"key":"e_1_2_2_67_1","first-page":"3D","article-title":"Thingi10K","volume":"10","author":"Zhou Qingnan","year":"2016","journal-title":"A Dataset of"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201359"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3306346.3323012","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3306346.3323012","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3306346.3323012","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:52Z","timestamp":1750206352000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3306346.3323012"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,12]]},"references-count":68,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,8,31]]}},"alternative-id":["10.1145\/3306346.3323012"],"URL":"https:\/\/doi.org\/10.1145\/3306346.3323012","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"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"}}]}}