{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T04:25:55Z","timestamp":1754108755518,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2020,11,27]],"date-time":"2020-11-27T00:00:00Z","timestamp":1606435200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["EF-1921728,DBI-1759836,RI-1618685"],"award-info":[{"award-number":["EF-1921728,DBI-1759836,RI-1618685"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>We present a novel algorithm for simplifying the topology of a 3D shape, which is characterized by the number of connected components, handles, and cavities. Existing methods either limit their modifications to be only cutting or only filling, or take a heuristic approach to decide where to cut or fill. We consider the problem of finding a globally optimal set of cuts and fills that achieve the simplest topology while minimizing geometric changes. We show that the problem can be formulated as graph labelling, and we solve it by a transformation to the Node-Weighted Steiner Tree problem. When tested on examples with varying levels of topological complexity, the algorithm shows notable improvement over existing simplification methods in both topological simplicity and geometric distortions.<\/jats:p>","DOI":"10.1145\/3414685.3417854","type":"journal-article","created":{"date-parts":[[2020,11,27]],"date-time":"2020-11-27T21:51:05Z","timestamp":1606513865000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["To cut or to fill"],"prefix":"10.1145","volume":"39","author":[{"given":"Dan","family":"Zeng","sequence":"first","affiliation":[{"name":"Washington University in St. Louis"}]},{"given":"Erin","family":"Chambers","sequence":"additional","affiliation":[{"name":"St. Louis University"}]},{"given":"David","family":"Letscher","sequence":"additional","affiliation":[{"name":"St. Louis University"}]},{"given":"Tao","family":"Ju","sequence":"additional","affiliation":[{"name":"Washington University in St. Louis"}]}],"member":"320","published-online":{"date-parts":[[2020,11,27]]},"reference":[{"volume-title":"11th DIMACS Implementation Challenge in Collaboration with ICERM: Steiner Tree Problems","key":"e_1_2_2_1_1","unstructured":"2014. 11th DIMACS Implementation Challenge in Collaboration with ICERM: Steiner Tree Problems . http:\/\/dimacs11.zib.de\/ 2014. 11th DIMACS Implementation Challenge in Collaboration with ICERM: Steiner Tree Problems. http:\/\/dimacs11.zib.de\/"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2014.08.010"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2431211.2431214"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973198.4"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/PCCGA.2002.1167868"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.969114"},{"key":"e_1_2_2_7_1","unstructured":"Erin W Chambers Tao Ju David Letscher Mao Li and Christopher Topp. 2018. Some Heuristics for the Homological Simplification Problem. In CCCG.  Erin W Chambers Tao Ju David Letscher Mao Li and Christopher Topp. 2018. Some Heuristics for the Homological Simplification Problem. In CCCG."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11866763_39"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/42.993130"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2003.1201824"},{"key":"e_1_2_2_11_1","unstructured":"Allen Hatcher. 2002. Algebraic Topology. Cambridge University Pres.  Allen Hatcher. 2002. Algebraic Topology. Cambridge University Pres."},{"key":"e_1_2_2_12_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3072959.3073644","article-title":"Topology-controlled Reconstruction of Multi-labelled Domains from Cross-sections","volume":"36","author":"Huang Zhiyang","year":"2017","unstructured":"Zhiyang Huang , Ming Zou , Nathan Carr , and Tao Ju . 2017 . Topology-controlled Reconstruction of Multi-labelled Domains from Cross-sections . ACM Transactions on Graphics (TOG) 36 , 4 (2017), 1 -- 12 . Zhiyang Huang, Ming Zou, Nathan Carr, and Tao Ju. 2017. Topology-controlled Reconstruction of Multi-labelled Domains from Cross-sections. ACM Transactions on Graphics (TOG) 36, 4 (2017), 1--12.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276430"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/nimg.2001.0831"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201348"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2017.0788"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2003.1196006"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-007-0102-8"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMI.2006.887364"},{"volume-title":"Eurographics.","author":"Sharf Andrei","key":"e_1_2_2_20_1","unstructured":"Andrei Sharf , Thomas Lewiner , Ariel Shamir , Leif Kobbelt , and Daniel Cohen-Or . 2006. Competing fronts for coarse-to-fine surface reconstruction . In Eurographics. Vienna , 389--398. http:\/\/www.mat.puc-rio.br\/~tomlew\/competing_fronts_eg.pdf Andrei Sharf, Thomas Lewiner, Ariel Shamir, Leif Kobbelt, and Daniel Cohen-Or. 2006. Competing fronts for coarse-to-fine surface reconstruction. In Eurographics. Vienna, 389--398. http:\/\/www.mat.puc-rio.br\/~tomlew\/competing_fronts_eg.pdf"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276431"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/42.963819"},{"volume-title":"Extraction of topologically simple isosurfaces from","author":"Szymczak Andrzej","key":"e_1_2_2_23_1","unstructured":"Andrzej Szymczak and James Vanderhyde . 2003. Extraction of topologically simple isosurfaces from volume datasets. In IEEE Visualization. 67-- 74 . Andrzej Szymczak and James Vanderhyde. 2003. Extraction of topologically simple isosurfaces from volume datasets. In IEEE Visualization. 67--74."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/990002.990007"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661241"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2008.07.008"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2007.1027"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766976"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3414685.3417854","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3414685.3417854","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3414685.3417854","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:15Z","timestamp":1750197795000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3414685.3417854"}},"subtitle":["a global optimization approach to topological simplification"],"short-title":[],"issued":{"date-parts":[[2020,11,27]]},"references-count":28,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3414685.3417854"],"URL":"https:\/\/doi.org\/10.1145\/3414685.3417854","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2020,11,27]]},"assertion":[{"value":"2020-11-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}