{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T16:07:10Z","timestamp":1772554030439,"version":"3.50.1"},"reference-count":108,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2015,6,22]],"date-time":"2015-06-22T00:00:00Z","timestamp":1434931200000},"content-version":"vor","delay-in-days":52,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Computer Graphics Forum"],"published-print":{"date-parts":[[2015,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Morse theory offers a natural and mathematically\u2010sound tool for shape analysis and understanding. It allows studying the behavior of a scalar function defined on a manifold. Starting from a Morse function, we can decompose the domain of the function into meaningful regions associated with the critical points of the function. Such decompositions, called Morse complexes, provide a segmentation of a shape and are extensively used in terrain modeling and in scientific visualization. Discrete Morse theory, a combinatorial counterpart of smooth Morse theory defined over cell complexes, provides an excellent basis for computing Morse complexes in a robust and efficient way. Moreover, since a discrete Morse complex computed over a given complex has the same homology as the original one, but fewer cells, discrete Morse theory is a fundamental tool for efficiently detecting holes in shapes through homology and persistent homology. In this survey, we review, classify and analyze algorithms for computing and simplifying Morse complexes in the context of such applications with an emphasis on discrete Morse theory and on algorithms based on it.<\/jats:p>","DOI":"10.1111\/cgf.12596","type":"journal-article","created":{"date-parts":[[2015,6,22]],"date-time":"2015-06-22T09:26:29Z","timestamp":1434965189000},"page":"761-785","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":65,"title":["Morse complexes for shape segmentation and homological analysis: discrete models and algorithms"],"prefix":"10.1111","volume":"34","author":[{"given":"Leila","family":"De Floriani","sequence":"first","affiliation":[{"name":"Department of Computer Science, Bioengineering, Robotics, and Systems Engineering University of Genova Genova Italy"}]},{"given":"Ulderico","family":"Fugacci","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Bioengineering, Robotics, and Systems Engineering University of Genova Genova Italy"}]},{"given":"Federico","family":"Iuricich","sequence":"additional","affiliation":[{"name":"Department of Computer Science and UMIACS University of Maryland College Park (MD) USA"}]},{"given":"Paola","family":"Magillo","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Bioengineering, Robotics, and Systems Engineering University of Genova Genova Italy"}]}],"member":"311","published-online":{"date-parts":[[2015,6,22]]},"reference":[{"key":"e_1_2_11_2_2","volume-title":"Computer Graphics and Geometric Modeling: Mathematics","author":"Agoston M.K.","year":"2005"},{"key":"e_1_2_11_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02021-0"},{"key":"e_1_2_11_4_2","doi-asserted-by":"crossref","first-page":"245","DOI":"10.4310\/jdg\/1214428092","article-title":"Critical points and curvature for embedded polyhedra","volume":"1","author":"Banchoff T.","year":"1967","journal-title":"J. of Differential Geometry"},{"key":"e_1_2_11_5_2","doi-asserted-by":"publisher","DOI":"10.2307\/2317380"},{"key":"e_1_2_11_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391731"},{"key":"e_1_2_11_7_2","first-page":"139","volume-title":"Proc. IEEE Visualization","author":"Bremer P.\u2010T.","year":"2003"},{"key":"e_1_2_11_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2004.3"},{"key":"e_1_2_11_9_2","first-page":"69","volume-title":"Computational Imaging and Vision","author":"Beucher S.","year":"1994"},{"issue":"1","key":"e_1_2_11_10_2","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/j.tcs.2007.10.018","article-title":"Reeb graphs for shape analysis and applications","volume":"392","author":"Biasotti S.","year":"2008","journal-title":"Theoretical Computer Science"},{"key":"e_1_2_11_11_2","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.2013.865281"},{"key":"e_1_2_11_12_2","first-page":"127","volume-title":"Symposuim on Computational Geometry 2013, SoCG \u201813, Rio de Janeiro, Brazil, June 17\u201320, 2013","author":"Burton B.A.","year":"2013"},{"key":"e_1_2_11_13_2","first-page":"300","volume-title":"Proc. Int. Conf. on Shape Modeling and Applications 2005 (SMI \u201805)","author":"Bremer P.\u2010T.","year":"2005"},{"key":"e_1_2_11_14_2","first-page":"51","volume-title":"Proc. IEEE Visualization'98","author":"Bajaj C.L.","year":"1998"},{"key":"e_1_2_11_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2010.253"},{"key":"e_1_2_11_16_2","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1145\/777792.777845","volume-title":"Proc. 9th Annual Symposium on Computational Geometry","author":"Cazals F.","year":"2003"},{"key":"e_1_2_11_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2012.03.010"},{"key":"e_1_2_11_18_2","volume-title":"Springer Briefs in Computer Science","author":"\u010comi\u0107 L.","year":"2014"},{"key":"e_1_2_11_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2011.03.009"},{"key":"e_1_2_11_20_2","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00697"},{"key":"e_1_2_11_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2011.05.001"},{"key":"e_1_2_11_22_2","first-page":"13","volume-title":"Lecture Notes in Computer Science","author":"\u010comi\u0107 L.","year":"2013"},{"key":"e_1_2_11_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0263-7855(86)80086-8"},{"key":"e_1_2_11_24_2","doi-asserted-by":"crossref","unstructured":"de BergM. TsirogiannisC.:Exact and approximate computations of watersheds on triangulated terrains. InProc. 19th ACM SIGSPATIAL Int. Conf. on Advances in Geographic Information Systems(2011) pp.74\u201383. 6 21","DOI":"10.1145\/2093973.2093985"},{"key":"e_1_2_11_25_2","first-page":"63","volume-title":"Proc. ACM GIS 2003 \u2010 The 11th Int. Symposium on Advances in Geographic Information Systems","author":"Danovaro E.","year":"2003"},{"key":"e_1_2_11_26_2","first-page":"386","volume-title":"Lecture Notes in Computer Science","author":"Danovaro E.","year":"2003"},{"key":"e_1_2_11_27_2","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1145\/1839778.1839806","volume-title":"Symposium on Solid and Physical Modeling","author":"Danovaro E.","year":"2010"},{"key":"e_1_2_11_28_2","doi-asserted-by":"crossref","DOI":"10.1007\/11863939_3","article-title":"A multi\u2010resolution representation for terrain morphology","volume":"2006","author":"Danovaro E.","year":"2006","journal-title":"Proc. fourth Int. Conf. on Geographic Information Science \u2010 GIScience"},{"key":"e_1_2_11_29_2","doi-asserted-by":"crossref","unstructured":"DanovaroE. De FlorianiL. VitaliM.:Multiresolution Morse\u2010Smale complexes for terrain modeling. In14th Int. Conf. on Image Analysis and Processing(2007). 20","DOI":"10.1109\/ICIAP.2007.4362801"},{"key":"e_1_2_11_30_2","unstructured":"DeyT.K. GiesenJ. GoswamiS.:Shape segmentation and matching with flow discretization. InAlgorithms and Data Structures 8th International Workshop WADS(2003) Dehne F. K. H. A. Sack J. Smid M. H. M.x (Eds.) pp.25\u201336. 6 7 19 21"},{"key":"e_1_2_11_31_2","first-page":"119","volume-title":"ACM Int. Conf. Proceeding Series","author":"De Floriani L.","year":"2005"},{"key":"e_1_2_11_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_11_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-010-9303-y"},{"key":"e_1_2_11_34_2","doi-asserted-by":"publisher","DOI":"10.2140\/agt.2007.7.339"},{"key":"e_1_2_11_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2013.04.009"},{"key":"e_1_2_11_36_2","doi-asserted-by":"publisher","DOI":"10.4310\/HHA.2014.v16.n1.a3"},{"key":"e_1_2_11_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9"},{"key":"e_1_2_11_38_2","first-page":"379","volume-title":"Algorithms and Combinatorics","author":"Edelsbrunner H.","year":"2003"},{"key":"e_1_2_11_39_2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/453\/08802"},{"key":"e_1_2_11_40_2","doi-asserted-by":"crossref","unstructured":"EdelsbrunnerH. HarerJ. NatarajanV. PascucciV.:Morse\u2010Smale complexes for piecewise linear 3\u2010manifolds. InProc. 19th ACM Symposium on Computational Geometry(2003) pp.361\u2013370. 5 6 21","DOI":"10.1145\/777792.777846"},{"key":"e_1_2_11_41_2","doi-asserted-by":"crossref","unstructured":"EdelsbrunnerH. HarerJ. ZomorodianA.:Hierarchical Morse complexes for piecewise linear 2\u2010manifolds. InProc. 17th ACM Symposium on Computational Geometry(2001) pp.70\u201379. 5 6 8 17 20 21","DOI":"10.1145\/378583.378626"},{"key":"e_1_2_11_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2885-2"},{"key":"e_1_2_11_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137878"},{"key":"e_1_2_11_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-012-0674-3"},{"key":"e_1_2_11_45_2","doi-asserted-by":"crossref","unstructured":"FugacciU. IuricichF. De FlorianiL.:Efficient computation of simplicial homology through acyclic matching. InSymbolic and Numeric Algorithms for Scientific Computing (SYNASC) 2014 16th International Symposium on(Sept2014) pp.587\u2013593. 10 12 13 21","DOI":"10.1109\/SYNASC.2014.84"},{"key":"e_1_2_11_46_2","doi-asserted-by":"crossref","unstructured":"FellegaraR. IuricichF. De FlorianiL. WeissK.:Efficient computation and simplification of discrete Morse decompositions on triangulated terrains. In22th ACM SIGSPATIAL Int. Symposium on Advances in Geographic Information Systems ACM\u2010GIS 2014 November 4\u20137 2014 Dallas Texas USA to appear(2014). 10 11 16 17","DOI":"10.1145\/2666310.2666412"},{"key":"e_1_2_11_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00004638"},{"key":"e_1_2_11_48_2","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1997.1650"},{"key":"e_1_2_11_49_2","first-page":"1405","volume-title":"Proceedings of the Symposium on Geometry Processing","author":"G\u0119bal K.","year":"2009"},{"key":"e_1_2_11_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2014.2346403"},{"key":"e_1_2_11_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2008.110"},{"key":"e_1_2_11_52_2","first-page":"67","volume-title":"Mathematics and Visualization","author":"Gyulassy A.","year":"2011"},{"key":"e_1_2_11_53_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2012.209"},{"key":"e_1_2_11_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2007.70603"},{"key":"e_1_2_11_55_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2014.2346434"},{"key":"e_1_2_11_56_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.01.002"},{"key":"e_1_2_11_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2011.272"},{"key":"e_1_2_11_58_2","doi-asserted-by":"crossref","unstructured":"GyulassyA. NatarajanV. PascucciV. BremerP. HamannB.:Topology\u2010based simplification for feature extraction from 3d scalar fields. In16th IEEE Visualization Conference (VIS 2005) 23\u201328 October 2005 Minneapolis MN USA(2005) p.68. 17 18","DOI":"10.1109\/VIS.2005.106"},{"key":"e_1_2_11_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2006.57"},{"key":"e_1_2_11_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2007.70552"},{"key":"e_1_2_11_61_2","unstructured":"GerstnerT. PaiarolaR.:Topology preserving and controlled topology simplifying multi\u2010resolution isosurface extraction. InProc. IEEE Visualization'00(2000) pp.259\u2013266. 20"},{"key":"e_1_2_11_62_2","unstructured":"G\u00fcntherD. ReininghausJ. SeidelH.\u2010P. WeinkaufT.:Notes on the simplification of the Morse\u2010Smale complex. InProc. TopoInVis(Davis U.S.A. March2013). 16 19"},{"key":"e_1_2_11_63_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-012-0726-8"},{"key":"e_1_2_11_64_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03222.x"},{"key":"e_1_2_11_65_2","unstructured":"G\u00fcntherD.:Topological analysis of discrete scalar data. PhD thesis 2012. Saarbr\u00fccken University Dissertation 2012. 17"},{"key":"e_1_2_11_66_2","first-page":"41","article-title":"The efficiency of a homology algorithm based on discrete Morse theory and coreductions","volume":"1","author":"Harker S.","year":"2010","journal-title":"Proceedings 3rd International Workshop on Computational Topology in Image Context (CTIC 2010). Image A"},{"key":"e_1_2_11_67_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-013-9145-0"},{"key":"e_1_2_11_68_2","unstructured":"IuricichF.:Multi\u2010resolution shape analysis based on discrete Morse decompositions. PhD thesis University of Genova \u2013 DIBRIS Italy 2014. 8 18 20"},{"key":"e_1_2_11_69_2","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.2005.10128941"},{"key":"e_1_2_11_70_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2011.249"},{"key":"e_1_2_11_71_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2006.186"},{"key":"e_1_2_11_72_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(03)00014-2"},{"key":"e_1_2_11_73_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2004.18"},{"key":"e_1_2_11_74_2","volume-title":"An Introduction to Morse Theory, vol. 208 of Translations of Mathematical Monographs","author":"Matsumoto Y.","year":"2002"},{"key":"e_1_2_11_75_2","doi-asserted-by":"publisher","DOI":"10.1016\/1047-3203(90)90014-M"},{"key":"e_1_2_11_76_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-008-9073-y"},{"key":"e_1_2_11_77_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89682-1_2"},{"key":"e_1_2_11_78_2","doi-asserted-by":"crossref","unstructured":"MagilloP. De FlorianiL. IuricichF.:Morphologically\u2010aware elimination of flat edges from a TIN. InProc. 21th ACM SIGSPATIAL Int. Conf. on Advances in Geographic Information Systems(2013) pp.244\u2013253. 8","DOI":"10.1145\/2525314.2525341"},{"key":"e_1_2_11_79_2","doi-asserted-by":"publisher","DOI":"10.1016\/0165-1684(94)90060-4"},{"key":"e_1_2_11_80_2","doi-asserted-by":"publisher","DOI":"10.1515\/9781400881802"},{"key":"e_1_2_11_81_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9529-6"},{"key":"e_1_2_11_82_2","doi-asserted-by":"publisher","DOI":"10.1063\/1.3445267"},{"key":"e_1_2_11_83_2","volume-title":"Advanced book classics","author":"Munkres J.","year":"1984"},{"key":"e_1_2_11_84_2","doi-asserted-by":"publisher","DOI":"10.1109\/2945.817348"},{"key":"e_1_2_11_85_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2010.09.036"},{"key":"e_1_2_11_86_2","first-page":"237","volume-title":"Mathematics and Visualization","author":"Natarajan V.","year":"2008"},{"key":"e_1_2_11_87_2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1002\/0470020288.ch8","volume-title":"Topological Data Structures for Surfaces","author":"Pascucci V.","year":"2004"},{"key":"e_1_2_11_88_2","unstructured":"ReininghausJ. G\u00fcntherD. HotzI. WeinkaufT. SeidelH.:Combinatorial gradient fields for 2d images with empirically convergent separatrices.CoRR abs\/1208.6523(2012). 9"},{"key":"e_1_2_11_89_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2011.269"},{"key":"e_1_2_11_90_2","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12398"},{"key":"e_1_2_11_91_2","doi-asserted-by":"crossref","first-page":"187","DOI":"10.3233\/FI-2000-411207","article-title":"The watershed transform: Definitions, algorithms, and parallelization strategies","volume":"41","author":"Roerdink J.","year":"2000","journal-title":"Fundamenta Informaticae"},{"key":"e_1_2_11_92_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2012.248"},{"key":"e_1_2_11_93_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2011.95"},{"key":"e_1_2_11_94_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1538-4632.2005.00638.x"},{"key":"e_1_2_11_95_2","unstructured":"SousbieT. ColombiS. PichonC.:The fully connected n\u2010dimensional skeleton: probing the evolution of the cosmic web.CoRR abs\/0809.2423(2008). 9 19"},{"key":"e_1_2_11_96_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2011.284"},{"key":"e_1_2_11_97_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03089.x"},{"key":"e_1_2_11_98_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-05088-0"},{"key":"e_1_2_11_99_2","first-page":"21","volume-title":"Proc. IEEE Visualization'00","author":"Stoev S.L.","year":"2000"},{"key":"e_1_2_11_100_2","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1002\/0470020288.ch4","volume-title":"Topological Data Structures for Surfaces","author":"Schneider B.","year":"2004"},{"key":"e_1_2_11_101_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.1995.cgf143_0181.x"},{"key":"e_1_2_11_102_2","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1145\/2261250.2261288","volume-title":"Proceedings of the Twenty\u2010eighth Annual Symposium on Computational Geometry","author":"Vegter G.","year":"2012"},{"key":"e_1_2_11_103_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25249-5_3"},{"key":"e_1_2_11_104_2","doi-asserted-by":"publisher","DOI":"10.1109\/34.87344"},{"key":"e_1_2_11_105_2","first-page":"92","volume-title":"GIS","author":"Weiss K.","year":"2011"},{"key":"e_1_2_11_106_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01528.x"},{"key":"e_1_2_11_107_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01702.x"},{"key":"e_1_2_11_108_2","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12123"},{"key":"e_1_2_11_109_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546945"}],"container-title":["Computer Graphics Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1111%2Fcgf.12596","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/cgf.12596","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T19:52:10Z","timestamp":1748461930000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1111\/cgf.12596"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5]]},"references-count":108,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,5]]}},"alternative-id":["10.1111\/cgf.12596"],"URL":"https:\/\/doi.org\/10.1111\/cgf.12596","archive":["Portico"],"relation":{},"ISSN":["0167-7055","1467-8659"],"issn-type":[{"value":"0167-7055","type":"print"},{"value":"1467-8659","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5]]},"assertion":[{"value":"2015-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}