{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T19:19:25Z","timestamp":1768677565542,"version":"3.49.0"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,7,30]],"date-time":"2018-07-30T00:00:00Z","timestamp":1532908800000},"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":["1657364"],"award-info":[{"award-number":["1657364"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011415","name":"Wayne State University","doi-asserted-by":"publisher","award":["4207299A"],"award-info":[{"award-number":["4207299A"]}],"id":[{"id":"10.13039\/100011415","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":[[2018,8,31]]},"abstract":"<jats:p>\n            This article presents a new method to compute a\n            <jats:italic>\n              self-intersection free high-dimensional Euclidean embedding (SIFHDE\n              <jats:sup>2<\/jats:sup>\n              )\n            <\/jats:italic>\n            for surfaces and volumes equipped with an arbitrary Riemannian metric. It is already known that given a high-dimensional (high-d) embedding, one can easily compute an anisotropic Voronoi diagram by back-mapping it to 3D space. We show here how to solve the inverse problem, i.e., given an input metric, compute a smooth intersection-free high-d embedding of the input such that the pullback metric of the embedding matches the input metric. Our numerical solution mechanism matches the deformation gradient of the 3D \u2192 higher-d mapping with the given Riemannian metric. We demonstrate the applicability of our method, by using it to construct anisotropic Restricted Voronoi Diagram (RVD) and anisotropic meshing, that are otherwise extremely difficult to compute. In SIFHDE\n            <jats:sup>2<\/jats:sup>\n            -space constructed by our algorithm, difficult 3D anisotropic computations are replaced with simple Euclidean computations, resulting in an isotropic RVD and its dual mesh on this high-d embedding. Results are compared with the state-of-the-art in anisotropic surface and volume meshings using several examples and evaluation metrics.\n          <\/jats:p>","DOI":"10.1145\/3197517.3201369","type":"journal-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T15:56:23Z","timestamp":1533052583000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Computing a high-dimensional euclidean embedding from an arbitrary smooth riemannian metric"],"prefix":"10.1145","volume":"37","author":[{"given":"Zichun","family":"Zhong","sequence":"first","affiliation":[{"name":"Wayne State University"}]},{"given":"Wenping","family":"Wang","sequence":"additional","affiliation":[{"name":"The University of Hong Kong"}]},{"given":"Bruno","family":"L\u00e9vy","sequence":"additional","affiliation":[{"name":"INRIA Nancy - Grand Est"}]},{"given":"Jing","family":"Hua","sequence":"additional","affiliation":[{"name":"Wayne State University"}]},{"given":"Xiaohu","family":"Guo","sequence":"additional","affiliation":[{"name":"University of Texas at Dallas"}]}],"member":"320","published-online":{"date-parts":[[2018,7,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2009.09.020"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2015.09.005"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882296"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073238"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2721895"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.08.006"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1377676.1377724"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/140955446"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-874X(96)00057-1"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-874X(96)00065-0"},{"key":"e_1_2_2_11_1","volume-title":"Proceedings of the National Academy of Sciences of the United States of America 109","author":"Borrelli V.","year":"2012","unstructured":"V. Borrelli , S. Jabrane , F. Lazarus , and B. Thibert . 2012. Flat Tori in Three-dimensional Space and Convex Integration . Proceedings of the National Academy of Sciences of the United States of America 109 , 19 ( 2012 ). V. Borrelli, S. Jabrane, F. Lazarus, and B. Thibert. 2012. Flat Tori in Three-dimensional Space and Convex Integration. Proceedings of the National Academy of Sciences of the United States of America 109, 19 (2012)."},{"key":"e_1_2_2_12_1","volume-title":"5th International Meshing Roundtable. 63--76","author":"Bossen F.","unstructured":"F. Bossen and P. Heckbert . 1996. A Pliant Method for Anisotropic Mesh Generation. In 5th International Meshing Roundtable. 63--76 . F. Bossen and P. Heckbert. 1996. A Pliant Method for Anisotropic Mesh Generation. In 5th International Meshing Roundtable. 63--76."},{"key":"e_1_2_2_13_1","first-page":"1","article-title":"Multigrid Multidimensional Scaling","volume":"0","author":"Bronstein M.","year":"2000","unstructured":"M. Bronstein , A. Bronstein , R. Kimmel , and I. Yavneh . 2000 . Multigrid Multidimensional Scaling . Numerical Linear Algebra with Applications 0 (2000), 1 -- 6 . M. Bronstein, A.Bronstein, R. Kimmel, and I. Yavneh. 2000. Multigrid Multidimensional Scaling. Numerical Linear Algebra with Applications 0 (2000), 1--6.","journal-title":"Numerical Linear Algebra with Applications"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the Copper Mountain Conference on Multigrid Methods.","author":"Bronstein M.","unstructured":"M. Bronstein , A. Bronstein , R. Kimmel , and I. Yavneh . 2005. A Multigrid Approach For Multi-Dimensional Scaling . In Proceedings of the Copper Mountain Conference on Multigrid Methods. M. Bronstein, A. Bronstein, R. Kimmel, and I. Yavneh. 2005. A Multigrid Approach For Multi-Dimensional Scaling. In Proceedings of the Copper Mountain Conference on Multigrid Methods."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2980245"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-006-0073-8"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-06-01896-5"},{"key":"e_1_2_2_18_1","first-page":"299","article-title":"Optimal Delaunay Triangulations","volume":"22","author":"Chen L.","year":"2004","unstructured":"L. Chen and J. Xu . 2004 . Optimal Delaunay Triangulations . Journal of Computational Mathematics 22 (2004), 299 -- 308 . L. Chen and J. Xu. 2004. Optimal Delaunay Triangulations. Journal of Computational Mathematics 22 (2004), 299--308.","journal-title":"Journal of Computational Mathematics"},{"key":"e_1_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Z. Chen W. Wang B. L\u00e9vy L. Liu and F. Sun. 2014. Revisiting Optimal Delaunay Triangulation for 3D Graded Mesh Generation. SIAM Journal Scientific Computing (2014).  Z. Chen W. Wang B. L\u00e9vy L. Liu and F. Sun. 2014. Revisiting Optimal Delaunay Triangulation for 3D Graded Mesh Generation. SIAM Journal Scientific Computing (2014).","DOI":"10.1137\/120875132"},{"key":"e_1_2_2_20_1","volume-title":"Dynamic Skin Triangulation. ACM-SIAM symposium on Discrete algorithms 25","author":"Cheng H-L.","year":"2001","unstructured":"H-L. Cheng , T. Dey , H. Edelsbrunner , and J. Sullivan . 2001 . Dynamic Skin Triangulation. ACM-SIAM symposium on Discrete algorithms 25 ( 2001 ), 525--568. H-L. Cheng, T. Dey, H. Edelsbrunner, and J. Sullivan. 2001. Dynamic Skin Triangulation. ACM-SIAM symposium on Discrete algorithms 25 (2001), 525--568."},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of ACM-SIAM Symposium on Discrete Algorithms. 202--211","author":"Cheng S.","unstructured":"S. Cheng , T. Dey , and E. Ramos . 2006. Anisotropic Surface Meshing . In Proceedings of ACM-SIAM Symposium on Discrete Algorithms. 202--211 . S. Cheng, T. Dey, and E. Ramos. 2006. Anisotropic Surface Meshing. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms. 202--211."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1141250.1642858"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-009-0323-7"},{"key":"e_1_2_2_24_1","volume-title":"23rd International Meshing Roundtable. 253--265","author":"Dassi F.","unstructured":"F. Dassi , A. Mola , and H. Si . 2014. Curvature-Adapted Remeshing of CAD Surfaces. In 23rd International Meshing Roundtable. 253--265 . F. Dassi, A. Mola, and H. Si. 2014. Curvature-Adapted Remeshing of CAD Surfaces. In 23rd International Meshing Roundtable. 253--265."},{"key":"e_1_2_2_25_1","volume-title":"24th International Meshing Roundtable. 265--277","author":"Dassi F.","unstructured":"F. Dassi , H. Si , S. Perotto , and T. Streckenbach . 2015. Anisotropic Finite Element Mesh Adaptation via Higher Dimensional Embedding. In 24th International Meshing Roundtable. 265--277 . F. Dassi, H. Si, S. Perotto, and T. Streckenbach. 2015. Anisotropic Finite Element Mesh Adaptation via Higher Dimensional Embedding. In 24th International Meshing Roundtable. 265--277."},{"key":"e_1_2_2_26_1","volume-title":"17th International Meshing Roundtable. 177--194","author":"Dobrzynski C.","unstructured":"C. Dobrzynski and P. Frey . 2008. Anisotropic Delaunay Mesh Adaptation for Unsteady Simulations. In 17th International Meshing Roundtable. 177--194 . C. Dobrzynski and P. Frey. 2008. Anisotropic Delaunay Mesh Adaptation for Unsteady Simulations. In 17th International Meshing Roundtable. 177--194."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144599352836"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827503428527"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2004.12.008"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1113046"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2004.11.025"},{"key":"e_1_2_2_32_1","volume-title":"6th International Meshing Roundtable. 363--373","author":"Frey P.","unstructured":"P. Frey and H. Borouchaki . 1997. Surface Mesh Evaluation. In 6th International Meshing Roundtable. 363--373 . P. Frey and H. Borouchaki. 1997. Surface Mesh Evaluation. In 6th International Meshing Roundtable. 363--373."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661235"},{"key":"e_1_2_2_34_1","unstructured":"G. Golub and C. Loan. 1996. Matrix Computations (3rd Ed.). Johns Hopkins University Press Baltimore Maryland.   G. Golub and C. Loan. 1996. Matrix Computations (3rd Ed.). Johns Hopkins University Press Baltimore Maryland."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1090\/bull\/1551"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1070\/RM1970v025n05ABEH003801"},{"key":"e_1_2_2_37_1","volume-title":"Isometric Embedding of Riemannian Manifolds in Euclidean Spaces","author":"Han Q.","unstructured":"Q. Han and J-X. Hong . 2006. Isometric Embedding of Riemannian Manifolds in Euclidean Spaces . Vol. 13 . American Mathematical Society . Q. Han and J-X. Hong. 2006. Isometric Embedding of Riemannian Manifolds in Euclidean Spaces. Vol. 13. American Mathematical Society."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00030-9"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.4310\/CAG.1993.v1.n4.a1"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0027763000022819"},{"key":"e_1_2_2_42_1","volume-title":"Proceedings of 16th International Meshing Roundtable. 3--23","author":"Klingner B.","unstructured":"B. Klingner and J. Shewchuk . 2007. Agressive Tetrahedral Mesh Improvement . In Proceedings of 16th International Meshing Roundtable. 3--23 . B. Klingner and J. Shewchuk. 2007. Agressive Tetrahedral Mesh Improvement. In Proceedings of 16th International Meshing Roundtable. 3--23."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1839778.1839797"},{"key":"e_1_2_2_44_1","volume-title":"Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen. 545--556","author":"Kuiper N.","year":"1955","unstructured":"N. Kuiper . 1955 . On C<sup>1<\/sup>-isometric Embeddings I . In Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen. 545--556 . N. Kuiper. 1955. On C<sup>1<\/sup>-isometric Embeddings I. In Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen. 545--556."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2015.10.004"},{"key":"e_1_2_2_46_1","volume-title":"21st International Meshing Roundtable. 349--366","author":"L\u00e9vy B.","unstructured":"B. L\u00e9vy and N. Bonneel . 2012. Variational Anisotropic Surface Meshing with Voronoi Parallel Linear Enumeration. In 21st International Meshing Roundtable. 349--366 . B. L\u00e9vy and N. Bonneel. 2012. Variational Anisotropic Surface Meshing with Voronoi Parallel Linear Enumeration. In 21st International Meshing Roundtable. 349--366."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589116"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559755.1559758"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_2_50_1","unstructured":"A. Loseille and R. L\u00f6hner. 2016. Anisotropic Mesh Generation for High-fidelity Simulations in CFD. INRIA (2016). preprint.  A. Loseille and R. L\u00f6hner. 2016. Anisotropic Mesh Generation for High-fidelity Simulations in CFD. INRIA (2016). preprint."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1002\/cnm.2549"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366171"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969840"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2017.02.004"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601179"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.proeng.2016.11.026"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1002\/cnm.2660"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/218013.218095"},{"key":"e_1_2_2_59_1","volume-title":"6th International Meshing Roundtable. 375--390","author":"Shimada K.","unstructured":"K. Shimada , A. Yamada , and T. Itoh . 1997. Anisotropic Triangular Meshing of Parametric Surfaces via Close Packing of Ellipsoidal Bubbles. In 6th International Meshing Roundtable. 375--390 . K. Shimada, A. Yamada, and T. Itoh. 1997. Anisotropic Triangular Meshing of Parametric Surfaces via Close Packing of Ellipsoidal Bubbles. In 6th International Meshing Roundtable. 375--390."},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-9274(94)90025-6"},{"key":"e_1_2_2_61_1","volume-title":"Proceedings of the fifth Eurographics symposium on Geometry processing. 109--116","author":"Sorkine-Hornung O.","unstructured":"O. Sorkine-Hornung and M. Alexa . 2007. As-rigid-as-possible Surface Modeling . In Proceedings of the fifth Eurographics symposium on Geometry processing. 109--116 . O. Sorkine-Hornung and M. Alexa. 2007. As-rigid-as-possible Surface Modeling. In Proceedings of the fifth Eurographics symposium on Geometry processing. 109--116."},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015736"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04319-2_10"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2007.70430"},{"key":"e_1_2_2_65_1","first-page":"2415","article-title":"Distance Preserving Embeddings for General n-Dimensional Manifolds","volume":"14","author":"Verma N.","year":"2012","unstructured":"N. Verma . 2012 . Distance Preserving Embeddings for General n-Dimensional Manifolds . Journal of Machine Learning Research volume 14 (2012), 2415 -- 2448 . N. Verma. 2012. Distance Preserving Embeddings for General n-Dimensional Manifolds. Journal of Machine Learning Research volume 14 (2012), 2415--2448.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_2_66_1","volume-title":"9th International Meshing Roundtable. 263--273","author":"Yamakawa S.","unstructured":"S. Yamakawa and K. Shimada . 2000. High Quality Anisotropic Tetrahedral Mesh Generation via Packing Ellipsoidal Bubbles. In 9th International Meshing Roundtable. 263--273 . S. Yamakawa and K. Shimada. 2000. High Quality Anisotropic Tetrahedral Mesh Generation via Packing Ellipsoidal Bubbles. In 9th International Meshing Roundtable. 263--273."},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.5555\/1735603.1735629"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2011.09.004"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461946"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2014.03.011"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3197517.3201369","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3197517.3201369","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3197517.3201369","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:45Z","timestamp":1750210785000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3197517.3201369"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,30]]},"references-count":69,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8,31]]}},"alternative-id":["10.1145\/3197517.3201369"],"URL":"https:\/\/doi.org\/10.1145\/3197517.3201369","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,30]]},"assertion":[{"value":"2018-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}