{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T14:49:51Z","timestamp":1776869391283,"version":"3.51.2"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2016,11,11]],"date-time":"2016-11-11T00:00:00Z","timestamp":1478822400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2016,11,11]]},"abstract":"<jats:p>\n            This paper presents a variational method to generate cell complexes with local anisotropy conforming to the Hessian of any given convex function and for any given local mesh density. Our formulation builds upon approximation theory to offer an anisotropic extension of Centroidal Voronoi Tessellations which can be seen as a dual form of Optimal Delaunay Triangulation. We thus refer to the resulting anisotropic polytopal meshes as\n            <jats:italic>Optimal Voronoi Tessellations.<\/jats:italic>\n            Our approach sharply contrasts with previous anisotropic versions of Voronoi diagrams as it employs first-type Bregman diagrams, a generalization of power diagrams where sites are augmented with not only a scalar-valued weight but also a vector-valued shift. As such, our OVT meshes contain only convex cells with straight edges, and admit an embedded dual triangulation that is combinatorially-regular. We show the effectiveness of our technique using off-the-shelf computational geometry libraries.\n          <\/jats:p>","DOI":"10.1145\/2980179.2980245","type":"journal-article","created":{"date-parts":[[2016,11,11]],"date-time":"2016-11-11T17:02:54Z","timestamp":1478883774000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Optimal voronoi tessellations with hessian-based anisotropy"],"prefix":"10.1145","volume":"35","author":[{"given":"Max","family":"Budninskiy","sequence":"first","affiliation":[{"name":"Caltech"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Beibei","family":"Liu","sequence":"additional","affiliation":[{"name":"Caltech"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fernando","family":"de Goes","sequence":"additional","affiliation":[{"name":"Pixar"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yiying","family":"Tong","sequence":"additional","affiliation":[{"name":"MSU"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Alliez","sequence":"additional","affiliation":[{"name":"Inria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathieu","family":"Desbrun","sequence":"additional","affiliation":[{"name":"Caltech\/Inria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,12,5]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073238"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733097"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187870"},{"key":"e_1_2_2_4_1","volume-title":"Tech. Rep. ACS-TR-362603, INRIA.","author":"Boissonnat J.-D.","year":"2006","unstructured":"Boissonnat , J.-D. , Cohen-Steiner , D. , and Yvinec , M . 2006 . Comparison of algorithms for anisotropic meshing and adaptive refinement. Tech. Rep. ACS-TR-362603, INRIA. Boissonnat, J.-D., Cohen-Steiner, D., and Yvinec, M. 2006. Comparison of algorithms for anisotropic meshing and adaptive refinement. Tech. Rep. ACS-TR-362603, INRIA."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.08.006"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115952.3115990"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2721895"},{"key":"e_1_2_2_8_1","unstructured":"Bossen Frank J. and Heckbert P. S. 1996. A pliant method for anisotropic mesh generation. In Int. Meshing Roundtable 63--76.  Bossen Frank J. and Heckbert P. S. 1996. A pliant method for anisotropic mesh generation. In Int. Meshing Roundtable 63--76."},{"key":"e_1_2_2_9_1","volume-title":"CGAL Editor","author":"User","unstructured":"CGAL. 2016. CGAL 4.8 User and Reference Manual. CGAL Editor ial Board , http:\/\/www.cgal.org. CGAL. 2016. CGAL 4.8 User and Reference Manual. CGAL Editorial Board, http:\/\/www.cgal.org."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2010.11.007"},{"key":"e_1_2_2_11_1","first-page":"299","article-title":"Optimal Delaunay triangulations","volume":"22","author":"Chen L.","year":"2004","unstructured":"Chen , L. , and Xu , J. 2004 . Optimal Delaunay triangulations . J. of Comp. Mathematics 22 , 2, 299 -- 308 . Chen, L., and Xu, J. 2004. Optimal Delaunay triangulations. J. of Comp. Mathematics 22, 2, 299--308.","journal-title":"J. of Comp. Mathematics"},{"key":"e_1_2_2_12_1","doi-asserted-by":"crossref","unstructured":"Chen L. Sun P. and Xu J. 2007. Optimal anisotropic simplicial meshes for minimizing interpolation errors in L<sup>p<\/sup>-norm. Math. of Comput. 76 257 179--204.  Chen L. Sun P. and Xu J. 2007. Optimal anisotropic simplicial meshes for minimizing interpolation errors in L<sup>p<\/sup> -norm. Math. of Comput. 76 257 179--204.","DOI":"10.1090\/S0025-5718-06-01896-5"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/120875132"},{"key":"e_1_2_2_14_1","unstructured":"Chen L. 2004. Mesh smoothing schemes based on Optimal Delaunay Triangulations. In Int. Meshing Roundtable 109--120.  Chen L. 2004. Mesh smoothing schemes based on Optimal Delaunay Triangulations. In Int. Meshing Roundtable 109--120."},{"key":"e_1_2_2_15_1","volume-title":"Symp. Disc. Alg., 202--211","author":"Cheng S.-W.","unstructured":"Cheng , S.-W. , Dey , T. K. , Ramos , E. A. , and Wenger , R . 2006. Anisotropic surface meshing . In Symp. Disc. Alg., 202--211 . Cheng, S.-W., Dey, T. K., Ramos, E. A., and Wenger, R. 2006. Anisotropic surface meshing. In Symp. Disc. Alg., 202--211."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.proeng.2015.10.138"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3037518.3037526"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366190"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461932"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766901"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.476"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827503428527"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144599352836"},{"key":"e_1_2_2_24_1","unstructured":"Frey P. and Alauzet F. 2004. Anisotropic metrics for mesh adaptation. In Comput. Fluid Solid Mech. K. Bathe Ed. 24--28.  Frey P. and Alauzet F. 2004. Anisotropic metrics for mesh adaptation. In Comput. Fluid Solid Mech. K. Bathe Ed. 24--28."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661235"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2012.07.001"},{"key":"e_1_2_2_27_1","volume-title":"World Congress on Comput. Mech..","author":"George P.","unstructured":"George , P. , Frey , P. , and Alauzet , F . 2002. Automatic generation of 3D adapted meshes . World Congress on Comput. Mech.. George, P., Frey, P., and Alauzet, F. 2002. Automatic generation of 3D adapted meshes. World Congress on Comput. Mech.."},{"key":"e_1_2_2_28_1","volume-title":"A Guide to Numerical Methods for Transport Equations","author":"Kuzmin D.","unstructured":"Kuzmin , D. 2010. A Guide to Numerical Methods for Transport Equations . University of Erlangen-Nuremberg. Kuzmin, D. 2010. A Guide to Numerical Methods for Transport Equations. University of Erlangen-Nuremberg."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/777792.777822"},{"key":"e_1_2_2_30_1","first-page":"443","article-title":"Regular triangulations of convex polytopes","volume":"4","author":"Lee C.","year":"1991","unstructured":"Lee , C. 1991 . Regular triangulations of convex polytopes . Applied Geom. & Disc. Math. 4 , 443 -- 456 . Lee, C. 1991. Regular triangulations of convex polytopes. Applied Geom. & Disc. Math. 4, 443--456.","journal-title":"Applied Geom. & Disc. Math."},{"key":"e_1_2_2_31_1","doi-asserted-by":"crossref","unstructured":"L\u00e9vy B. and Bonneel N. 2013. Variational anisotropic surface meshing with Voronoi parallel linear enumeration. In Int. Meshing Roundtable. 349--366.  L\u00e9vy B. and Bonneel N. 2013. Variational anisotropic surface meshing with Voronoi parallel linear enumeration. In Int. Meshing Roundtable. 349--366.","DOI":"10.1007\/978-3-642-33573-0_21"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778856"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559755.1559758"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461927"},{"key":"e_1_2_2_35_1","doi-asserted-by":"crossref","unstructured":"Loseille A. and Alauzet F. 2009. Optimal 3D highly anisotropic mesh adaptation based on the continuous mesh framework. In Int. Meshing Roundtable. 575--594.  Loseille A. and Alauzet F. 2009. Optimal 3D highly anisotropic mesh adaptation based on the continuous mesh framework. In Int. Meshing Roundtable. 575--594.","DOI":"10.1007\/978-3-642-04319-2_33"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/090754078"},{"key":"e_1_2_2_37_1","unstructured":"Marsden J. E. and Tromba A. 2003. Vector Calculus 5th ed. W. H. Freeman.  Marsden J. E. and Tromba A. 2003. Vector Calculus 5th ed. W. H. Freeman."},{"key":"e_1_2_2_38_1","doi-asserted-by":"crossref","unstructured":"Memari P. Mullen P. and Desbrun M. 2012. Parametrization of generalized primal-dual triangulations. In Int. Meshing Roundtable. 237--253.  Memari P. Mullen P. and Desbrun M. 2012. Parametrization of generalized primal-dual triangulations. In Int. Meshing Roundtable. 237--253.","DOI":"10.1007\/978-3-642-24734-7_13"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2011-02459-2"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964998"},{"key":"e_1_2_2_41_1","volume-title":"Academic","author":"Nadler E.","unstructured":"Nadler , E. 1986. Piecewise linear best L<sub>2<\/sub> approximation on triangulations . In Approx. Theory V, C. K. Chui, L. L. Schumaker, and J. D. Ward, Eds. Academic Press , 499--502. Nadler, E. 1986. Piecewise linear best L<sub>2<\/sub> approximation on triangulations. In Approx. Theory V, C. K. Chui, L. L. Schumaker, and J. D. Ward, Eds. Academic Press, 499--502."},{"key":"e_1_2_2_42_1","doi-asserted-by":"crossref","unstructured":"Nielsen F. and Nock R. 2011. Skew Jensen-Bregman Voronoi diagrams. In Transactions on Computational Science XIV Special Issue on Voronoi Diagrams and Delaunay Triangulation M. L. Gavrilova C. J. K. Tan and M. A. Mostafavi Eds. Springer 102--128.   Nielsen F. and Nock R. 2011. Skew Jensen-Bregman Voronoi diagrams. In Transactions on Computational Science XIV Special Issue on Voronoi Diagrams and Delaunay Triangulation M. L. Gavrilova C. J. K. Tan and M. A. Mostafavi Eds. Springer 102--128.","DOI":"10.1007\/978-3-642-25249-5_4"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2014.09.009"},{"key":"e_1_2_2_44_1","first-page":"4","article-title":"Voro++: A three-dimensional Voronoi cell library in C++. Chaos","volume":"19","author":"Rycroft C. H.","year":"2009","unstructured":"Rycroft , C. H. 2009 . Voro++: A three-dimensional Voronoi cell library in C++. Chaos : An Interdisciplinary Journal of Nonlinear Science 19 , 4 . Rycroft, C. H. 2009. Voro++: A three-dimensional Voronoi cell library in C++. Chaos: An Interdisciplinary Journal of Nonlinear Science 19, 4.","journal-title":"An Interdisciplinary Journal of Nonlinear Science"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276894"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2011.09.007"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531381"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2007.70430"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2011.09.004"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461946"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2980179.2980245","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2980179.2980245","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:49:57Z","timestamp":1750218597000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2980179.2980245"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,11]]},"references-count":50,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2016,11,11]]}},"alternative-id":["10.1145\/2980179.2980245"],"URL":"https:\/\/doi.org\/10.1145\/2980179.2980245","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,11]]},"assertion":[{"value":"2016-12-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}