{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T02:58:45Z","timestamp":1778641125630,"version":"3.51.4"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T00:00:00Z","timestamp":1446422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE2013-T2-2-011 & AcRF 40\/12"],"award-info":[{"award-number":["MOE2013-T2-2-011 & AcRF 40\/12"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61432003 & 61322206"],"award-info":[{"award-number":["61432003 & 61322206"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2015,11,4]]},"abstract":"<jats:p>\n            Delaunay meshes (DM) are a special type of triangle mesh where the local Delaunay condition holds everywhere. We present an efficient algorithm to convert an arbitrary manifold triangle mesh\n            <jats:italic>M<\/jats:italic>\n            into a Delaunay mesh. We show that the constructed DM has\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>Kn<\/jats:italic>\n            ) vertices, where\n            <jats:italic>n<\/jats:italic>\n            is the number of vertices in\n            <jats:italic>M<\/jats:italic>\n            and\n            <jats:italic>K<\/jats:italic>\n            is a model-dependent constant. We also develop a novel algorithm to simplify Delaunay meshes, allowing a smooth choice of detail levels. Our methods are conceptually simple, theoretically sound and easy to implement. The DM construction algorithm also scales well due to its\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>nK<\/jats:italic>\n            log\n            <jats:italic>K<\/jats:italic>\n            ) time complexity.\n          <\/jats:p>\n          <jats:p>Delaunay meshes have many favorable geometric and numerical properties. For example, a DM has exactly the same geometry as the input mesh, and it can be encoded by any mesh data structure. Moreover, the empty geodesic circumcircle property implies that the commonly used cotangent Laplace-Beltrami operator has non-negative weights. Therefore, the existing digital geometry processing algorithms can benefit the numerical stability of DM without changing any codes. We observe that DMs can improve the accuracy of the heat method for computing geodesic distances. Also, popular parameterization techniques, such as discrete harmonic mapping, produce more stable results on the DMs than on the input meshes.<\/jats:p>","DOI":"10.1145\/2816795.2818076","type":"journal-article","created":{"date-parts":[[2015,10,27]],"date-time":"2015-10-27T12:36:39Z","timestamp":1445949399000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":51,"title":["Efficient construction and simplification of Delaunay meshes"],"prefix":"10.1145","volume":"34","author":[{"given":"Yong-Jin","family":"Liu","sequence":"first","affiliation":[{"name":"Tsinghua University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chun-Xu","family":"Xu","sequence":"additional","affiliation":[{"name":"Tsinghua University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dian","family":"Fan","sequence":"additional","affiliation":[{"name":"Tsinghua University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"He","sequence":"additional","affiliation":[{"name":"Nanyang Technological University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,11,2]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009475"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-007-9006-1"},{"key":"e_1_2_2_3_1","first-page":"66","article-title":"Polyhedral embedding of a net","volume":"15","author":"Burago Y. D.","year":"1960","unstructured":"Burago , Y. D. , and Zallgaller , V. A. 1960 . Polyhedral embedding of a net . Vestnik Leningrad. Univ. 15 , 66 -- 80 . Burago, Y. D., and Zallgaller, V. A. 1960. Polyhedral embedding of a net. Vestnik Leningrad. Univ. 15, 66--80.","journal-title":"Vestnik Leningrad. Univ."},{"key":"e_1_2_2_4_1","unstructured":"Cheng S.-W. Dey T. K. and Shewchuk J. R. 2012. Delaunay Mesh Generation. CRC Press.   Cheng S.-W. Dey T. K. and Shewchuk J. R. 2012. Delaunay Mesh Generation. CRC Press."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/41958.41981"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/160985.161150"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00236"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2516971.2516977"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366190"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461932"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2602143"},{"key":"e_1_2_2_12_1","first-page":"23","article-title":"Topology preserving edge contraction","volume":"66","author":"Dey T. K.","year":"1999","unstructured":"Dey , T. K. , Edelsbrunner , H. , Guha , S. , and Nekhayev , D. V. 1999 . Topology preserving edge contraction . Publ. Inst. Math.(Beograd) (N.S) 66 , 80, 23 -- 45 . Dey, T. K., Edelsbrunner, H., Guha, S., and Nekhayev, D. V. 1999. Topology preserving edge contraction. Publ. Inst. Math.(Beograd) (N.S) 66, 80, 23--45.","journal-title":"Publ. Inst. Math.(Beograd) (N.S)"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827503428527"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of SGP '07","author":"Dyer R.","unstructured":"Dyer , R. , Zhang , H. , and M\u00f6ller , T . 2007. Delaunay mesh construction . In Proceedings of SGP '07 , 273--282. Dyer, R., Zhang, H., and M\u00f6ller, T. 2007. Delaunay mesh construction. In Proceedings of SGP '07, 273--282."},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of SGP'08","author":"Dyer R.","unstructured":"Dyer , R. , Zhang , H. , and M\u00f6ller , T . 2008. Surface sampling and the intrinsic Voronoi diagram . In Proceedings of SGP'08 , 1393--1402. Dyer, R., Zhang, H., and M\u00f6ller, T. 2008. Surface sampling and the intrinsic Voronoi diagram. In Proceedings of SGP'08, 1393--1402."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195997000223"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-007-0249-8"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/258734.258849"},{"key":"e_1_2_2_19_1","unstructured":"Glickenstein D. 2005. Geometric triangulations and discrete Laplacians on manifolds. arXiv:math\/0508188.  Glickenstein D. 2005. Geometric triangulations and discrete Laplacians on manifolds. arXiv:math\/0508188."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758770"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/500525.500550"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778856"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559755.1559758"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.221"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461927"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2012.28"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.05.012"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964998"},{"key":"e_1_2_2_30_1","volume-title":"-N","author":"Okabe A.","year":"2000","unstructured":"Okabe , A. , Boots , B. , Sugihara , K. , and Chiu , S . -N . 2000 . Spatial Tessellations : Concept and Applications of Voronoi Diagrams. Wiley . Okabe, A., Boots, B., Sugihara, K., and Chiu, S.-N. 2000. Spatial Tessellations: Concept and Applications of Voronoi Diagrams. Wiley."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.1993.10504266"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(90)90011-F"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.2307\/2118572"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2008.08.004"},{"key":"e_1_2_2_35_1","volume-title":"Proceedings of IMR '07","author":"VanderZee E.","unstructured":"VanderZee , E. , Hirani , A. N. , Guoy , D. , and Ramos , E . 2007. Well-centered planar triangulation-an iterative approach . In Proceedings of IMR '07 , 121--138. VanderZee, E., Hirani, A. N., Guoy, D., and Ramos, E. 2007. Well-centered planar triangulation-an iterative approach. In Proceedings of IMR '07, 121--138."},{"key":"e_1_2_2_36_1","volume-title":"Proceedings of SGP '07","author":"Wardetzky M.","unstructured":"Wardetzky , M. , Mathur , S. , K\u00e4lberer , F. , and Grinspun , E . 2007. Discrete laplace operators: No free lunch . In Proceedings of SGP '07 , 33--37. Wardetzky, M., Mathur, S., K\u00e4lberer, F., and Grinspun, E. 2007. Discrete laplace operators: No free lunch. In Proceedings of SGP '07, 33--37."},{"key":"e_1_2_2_37_1","volume-title":"Proceedings of SGP '09","author":"Yan D.-M.","unstructured":"Yan , D.-M. , L\u00e9vy , B. , Liu , Y. , Sun , F. , and Wang , W . 2009. Isotropic remeshing with fast and exact computation of restricted Voronoi diagram . In Proceedings of SGP '09 , 1445--1454. Yan, D.-M., L\u00e9vy, B., Liu, Y., Sun, F., and Wang, W. 2009. Isotropic remeshing with fast and exact computation of restricted Voronoi diagram. In Proceedings of SGP '09, 1445--1454."},{"key":"e_1_2_2_38_1","volume-title":"Proceedings of the Sixth Annual Conference of the Romanian Society of Mathematical Sciences, 9--17","author":"Zamfirescu T.","year":"2002","unstructured":"Zamfirescu , T. 2002 . Acute triangulations: a short survey . In Proceedings of the Sixth Annual Conference of the Romanian Society of Mathematical Sciences, 9--17 . Zamfirescu, T. 2002. Acute triangulations: a short survey. In Proceedings of the Sixth Annual Conference of the Romanian Society of Mathematical Sciences, 9--17."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2816795.2818076","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2816795.2818076","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:18Z","timestamp":1750225698000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2816795.2818076"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,2]]},"references-count":38,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2015,11,4]]}},"alternative-id":["10.1145\/2816795.2818076"],"URL":"https:\/\/doi.org\/10.1145\/2816795.2818076","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,2]]},"assertion":[{"value":"2015-11-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}