{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T21:17:10Z","timestamp":1764969430743,"version":"3.46.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101055448"],"award-info":[{"award-number":["101055448"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100019239","name":"Berlin Mathematics Research Center MATH+","doi-asserted-by":"crossref","award":["390685689"],"award-info":[{"award-number":["390685689"]}],"id":[{"id":"10.13039\/501100019239","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":[[2025,12]]},"abstract":"<jats:p>\n                    We show how the problem of creating a triangulation in\n                    <jats:italic toggle=\"yes\">d<\/jats:italic>\n                    -dimensional space that conforms to constraints given as sub-simplices can be turned into the problem of computing the lower hull of a sum of wedge functions. This sum can be interpreted as a Weighted Delaunay Triangulations, necessarily containing the constraints as unions of its elements. Intersections of wedges lead to Steiner points. As the number of such intersections is polynomial in the number of wedges, and the number of wedges per element is typically 1 (at most\n                    <jats:italic toggle=\"yes\">d<\/jats:italic>\n                    ), this proves that the complexity of the output is polynomial. Moreover, we show that the majority of wedge intersections is unnecessary for a conforming triangulation and further heuristically reduce the number of Steiner points. Using appropriate data structures, the function can be evaluated in quasi-linear time, leading to an output-sensitive algorithm.\n                  <\/jats:p>","DOI":"10.1145\/3763368","type":"journal-article","created":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T17:15:39Z","timestamp":1764868539000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Sums of Wedges: Conforming Weighted Delaunay Triangulations are Polynomial in Fixed Dimension"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8920-5544","authenticated-orcid":false,"given":"Dimitrios","family":"Bogiokas","sequence":"first","affiliation":[{"name":"Technical University of Berlin, Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7098-1524","authenticated-orcid":false,"given":"Ugo","family":"Finnendahl","sequence":"additional","affiliation":[{"name":"Technical University of Berlin, Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-3457-4829","authenticated-orcid":false,"given":"Thorsten","family":"Seidelmann","sequence":"additional","affiliation":[{"name":"TU Berlin, Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9854-8466","authenticated-orcid":false,"given":"Marc","family":"Alexa","sequence":"additional","affiliation":[{"name":"Technical University of Berlin, Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2025,12,4]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"360","article-title":"On the surfaces representable as difference of convex functions","volume":"9","author":"Aleksandrov Aleksandr Danilovich","year":"2012","unstructured":"Aleksandr Danilovich Aleksandrov. 2012. On the surfaces representable as difference of convex functions. Sibirskie Elektronnye Matematicheskie Izvestiia 9 (2012), 360\u20133376. English translation of original 1949 article..","journal-title":"Sibirskie Elektronnye Matematicheskie Izvestiia"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417776"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073238"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2020.102856"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50006-1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","unstructured":"Franz Aurenhammer Rolf Klein and Der-Tsai Lee. 2013. Voronoi Diagrams and Delaunay Triangulations. WORLD SCIENTIFIC. 10.1142\/8685","DOI":"10.1142\/8685"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542362.1542403"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/24.2.162"},{"key":"e_1_2_1_9_1","unstructured":"Herv\u00e9 Br\u00f6nnimann Andreas Fabri Geert-Jan Giezeman Susan Hert Michael Hoffmann Lutz Kettner Sylvain Pion and Stefan Schirra. 2023. 2D and 3D Linear Geometry Kernel. In CGAL User and Reference Manual (5.6 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/5.6\/Manual\/packages.html#PkgKernel23"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213031"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573985"},{"key":"e_1_2_1_12_1","volume-title":"Delaunay Mesh Generation","author":"Cheng Siu-Wing","unstructured":"Siu-Wing Cheng, Tamal K. Dey, and Jonathan Shewchuk. 2012. Delaunay Mesh Generation (1st ed.). Chapman & Hall\/CRC.","edition":"1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/41958.41981"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/160985.161150"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/513400.513425"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2602143"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12971-1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Olivier Devillers Sylvain Pion and Monique Teillaud. 2001. Walking in a triangulation. Technical Report RR-4120. INRIA. https:\/\/hal.inria.fr\/inria-00072509","DOI":"10.1145\/378583.378643"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3478513.3480564"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618352"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511530067"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187681"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/142675.142688"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573974"},{"key":"e_1_2_1_25_1","volume-title":"GNU MP: The GNU Multiple Precision Arithmetic Library (6.2.1 ed.). https:\/\/gmplib.org\/","author":"Torbj\u00f6rn Granlund","year":"2020","unstructured":"Torbj\u00f6rn Granlund et al. 2020. GNU MP: The GNU Multiple Precision Arithmetic Library (6.2.1 ed.). https:\/\/gmplib.org\/"},{"key":"e_1_2_1_26_1","unstructured":"Yixin Hu Teseo Schneider Bolun Wang Denis Zorin and Daniele Panozzo. 2019. Fast Tetrahedral Meshing in the Wild. arXiv:1908.03581 [cs.GR]"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201353"},{"key":"e_1_2_1_28_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"},{"key":"e_1_2_1_29_1","unstructured":"Cl\u00e9ment Jamin Sylvain Pion and Monique Teillaud. 2023. 3D Triangulations. In CGAL User and Reference Manual (5.6 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/5.6\/Manual\/packages.html#PkgTriangulation3"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-4817-3_5"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276448"},{"volume-title":"Control","author":"Miller Gary L.","key":"e_1_2_1_32_1","unstructured":"Gary L. Miller. 1998. Control volume meshes using sphere packing. In Solving Irregularly Structured Problems in Parallel, Alfonso Ferreira, Jos\u00e9 Rolim, Horst Simon, and Shang-Hua Teng (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 128\u2013131."},{"key":"e_1_2_1_33_1","volume-title":"Gable","author":"Murphy Michael","year":"2000","unstructured":"Michael Murphy, David M. Mount, and Carl W. Gable. 2000. A Point-Placement Strategy for Conforming Delaunay Tetrahedralization. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, USA, 67?74."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/262839.263061"},{"volume-title":"Goodman, Jacob E.","author":"Rambau J\u00f6rg","key":"e_1_2_1_35_1","unstructured":"J\u00f6rg Rambau. 2005. On a generalization of Sch\u00f6nhardt's polyhedron. In Goodman, Jacob E.; Pach, J\u00e1nos; Welzl, Emo (Hrsg.): Combinatorial and computational geometry. Mathematical Sciences Research Institute Publications, Vol. 52. Cambridge Univ. Press, Cambridge, 501\u2013516."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1021"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187840"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01451597"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009321"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276893"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276894"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/777792.777821"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-008-9060-3"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582138"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.finel.2009.06.017"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629697"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29090-7_9"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/24.2.167"},{"key":"e_1_2_1_49_1","first-page":"3D","article-title":"Thingi10K","volume":"10","author":"Zhou Qingnan","year":"2016","unstructured":"Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797.","journal-title":"A Dataset of"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8431-1"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763368","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T21:14:51Z","timestamp":1764969291000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763368"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12]]},"references-count":50,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10.1145\/3763368"],"URL":"https:\/\/doi.org\/10.1145\/3763368","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2025,12]]},"assertion":[{"value":"2025-05-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-09","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}