×

zbMATH — the first resource for mathematics

Categorified Reeb graphs. (English) Zbl 1350.68271
Summary: The Reeb graph is a construction which originated in Morse theory to study a real-valued function defined on a topological space. More recently, it has been used in various applications to study noisy data which creates a desire to define a measure of similarity between these structures. Here, we exploit the fact that the category of Reeb graphs is equivalent to the category of a particular class of cosheaf. Using this equivalency, we can define an ‘interleaving’ distance between Reeb graphs which is stable under the perturbation of a function. Along the way, we obtain a natural construction for smoothing a Reeb graph to reduce its topological complexity. The smoothed Reeb graph can be constructed in polynomial time.

MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
18F20 Presheaves and sheaves, stacks, descent conditions (category-theoretic aspects)
57M50 General geometric structures on low-dimensional manifolds
Software:
ReebHanTun
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Acar, U.A., Blelloch, G.E., Harper, R., Vittes, J.L., Woo, S.L.M.: Dynamizing static algorithms, with applications to dynamic trees and history independence. In: ACM-SIAM Symposium on Discrete Algorithms, SODA ’04, pp. 531-540 (2004) · Zbl 1318.68080
[2] Agarwal, P.K., Edelsbrunner, H., Harer, J., Wang, Y.: Extreme elevation on a 2-manifold. In: Proceedings of the Twentieth Annual Symposium on Computational Geometry, SoCG ’04, pp. 357-365, New York, NY. ACM (2004) · Zbl 1377.68258
[3] Alstrup, S; Holm, J; Lichtenberg, K; Thorup, M, Maintaining information in fully dynamic trees with top trees, ACM Trans. Algorithms, 1, 243-264, (2005) · Zbl 1321.68211
[4] Bauer, U., Ge, X., Wang, Y.: Measuring distance between Reeb graphs. In: Proceedings of the Thirtieth Annual Symposium on Computational Geometry, SoCG ’14 (2014) · Zbl 1395.68288
[5] Bauer, U., Munch, E., Wang, Y.: Strong equivalence of the interleaving and functional distortion metrics for Reeb graphs. In: Arge, Lars, Pach, János (eds.) 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), vol. 34, pp. 461-475. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2015) · Zbl 1382.58010
[6] Biasotti, S; Falcidieno, B; Spagnuolo, M; Borgefors, G (ed.); Nyström, I (ed.); Baja, GS (ed.), Extended Reeb graphs for surface understanding and description, No. 1952, 185-197, (2000), Berlin · Zbl 1043.68785
[7] Biasotti, S; Giorgi, D; Spagnuolo, M; Falcidieno, B, Reeb graphs for shape analysis and applications, Theor. Comput. Sci. Comput. Algebr. Geom. Appl., 392, 5-22, (2008) · Zbl 1134.68064
[8] Bubenik, P; Scott, JA, Categorification of persistent homology, Discrete Comput. Geom., 51, 600-627, (2014) · Zbl 1295.55005
[9] Bubenik, P; Silva, V; Scott, J, Metrics for generalized persistence modules, Found. Comput. Math., 15, 1501-1531, (2014) · Zbl 1345.55006
[10] Burghelea, D; Dey, TK, Topological persistence for circle-valued maps, Discrete Comput. Geom., 50, 69-98, (2013) · Zbl 1275.55009
[11] Carlsson, G., de Silva, V., Morozov, D.: Zigzag persistent homology and real-valued functions. In: Proceedings 25th ACM Symposium on Computational Geometry (SoCG), pp. 247-256 (2009) · Zbl 1380.68385
[12] Carr, H., Snoeyink, J., Axen, U.: Computing contour trees in all dimensions. Comput. Geom. 24(2), 75-94 (2003). Special Issue on the Fourth CGC Workshop on Computational Geometry. https://graphics.stanford.edu/courses/cs468-03-winter/Papers/carr-contour-soda.pdf · Zbl 1052.68098
[13] Chazal, F., Sun, J.: Gromov-Hausdorff approximation of filament structure using Reeb-type graph. In: Proceedings of the Thirtieth Annual Symposium on Computational Geometry, SOCG’14, pp. 491:491-491:500. ACM, New York, NY (2014) · Zbl 1395.68296
[14] Chazal, F., Cohen-Steiner, D., Glisse, M., Guibas, L.J., Oudot, S.Y.: Proximity of persistence modules and their diagrams. In: Proceedings of the 25th annual symposium on computational geometry, SoCG ’09, pp. 237-246. ACM, New York, NY (2009) · Zbl 1380.68387
[15] Cohen-Steiner, D; Edelsbrunner, H; Harer, J, Stability of persistence diagrams, Discrete Comput. Geom., 37, 103-120, (2007) · Zbl 1117.54027
[16] Cohen-Steiner, D; Edelsbrunner, H; Harer, J, Extending persistence using Poincaré and Lefschetz duality, Found. Comput. Math., 9, 79-103, (2009) · Zbl 1189.55002
[17] Cole-McLaughlin, K., Edelsbrunner, H., Harer, J., Natarajan, V., Pascucci, V.: Loops in Reeb graphs of 2-manifolds. In: Proceedings of the Nineteenth Annual Symposium on Computational Geometry, SoCG ’03, pp. 344-350. ACM, New York, NY (2003) · Zbl 1379.57025
[18] Coste, M.: An Introduction to o-minimal Geometry. Istituti Editoriali e Poligrafici Internazionali, Pisa (2000)
[19] Curry, J: Sheaves, Cosheaves and Applications. PhD thesis, University of Pennsylvania (2014)
[20] Dey, TK; Fan, F; Wang, Y, An efficient computation of handle and tunnel loops via Reeb graphs, ACM Trans. Graph., 32, 32:1-32:10, (2013) · Zbl 1305.68226
[21] Di Fabio, B., Landi, C.: The edit distance for Reeb graphs of surfaces. arXiv:1411.1544 (2014) · Zbl 1332.05038
[22] Doraiswamy, H; Natarajan, V, Output-sensitive construction of Reeb graphs, IEEE Trans. Vis. Comput. Graph., 18, 146-159, (2012) · Zbl 1183.68658
[23] Edelsbrunner, H., Harer, J., Patel, A.: Reeb spaces of piecewise linear mappings. In: Proceedings of the Twenty-fourth Annual Symposium on Computational Geometry, SoCG ’08, pp. 242-250. ACM, New York, NY (2008) · Zbl 1271.57059
[24] Eppstein, D; Galil, Z; Italiano, GF; Nissenzweig, A, Sparsification: a technique for speeding up dynamic graph algorithms, J. ACM, 44, 669-696, (1997) · Zbl 0891.68072
[25] Escolano, F; Hancock, ER; Biasotti, S; Wilson, R (ed.); Hancock, E (ed.); Bors, A (ed.); Smith, W (ed.), Complexity fusion for indexing Reeb digraphs, No. 8047, 120-127, (2013), Berlin
[26] Fox, R.H.: Covering spaces with singularities. In: Algebraic Geometry and Topology: A Symposium in Honor of S. Lefschetz, pp. 243-257 (1957) · Zbl 0079.16505
[27] Funk, J, The display locale of a cosheaf, Cah. Topologie et Géom. Différ. Catégoriques, 36, 53-93, (1995) · Zbl 0824.18005
[28] Ge, X., Safa, I.I., Belkin, M., Wang, Y.: Data skeletonization via Reeb graphs. In: Shawe-Taylor, J., Zemel, R.S., Bartlett, P., Pereira, F.C.N., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems, vol. 24, pp. 837-845 (2011) · Zbl 1204.18008
[29] Grothendieck, A.: A General Theory of Fibre Spaces With Structure Sheaf. University of Kansas, Lawrence, KS (1955)
[30] Harvey, W., Wang, Y.: Topological landscape ensembles for visualization of scalar-valued functions. In: Proceedings of the 12th Eurographics/IEEE—VGTC Conference on Visualization, EuroVis’10, pp. 993-1002, Aire-la-Ville, Switzerland. Eurographics Association (2010) · Zbl 1305.68226
[31] Harvey, W., Wang, Y., Wenger, R.: A randomized \(O(m \log m)\) time algorithm for computing Reeb graphs of arbitrary simplicial complexes. In: Proceedings of the 2010 Annual Symposium on Computational Geometry, SoCG ’10, pp. 267-276. ACM, New York, NY (2010) · Zbl 1284.68600
[32] Hilaga, M., Shinagawa, Y., Kohmura, T., Kunii, T.L.: Topology matching for fully automatic similarity estimation of 3D shapes. In: Proceedings of the 28th Annual Conference on Computer graphics and Interactive Techniques, SIGGRAPH ’01, pp. 203-212. ACM, New York, NY (2001)
[33] Johnstone, P.T.: Stone Spaces. Cambridge Studies in Advanced Mathematics, vol. 3. Cambridge University Press, Cambridge (1986) · Zbl 0586.54001
[34] Kashiwara, M., Schapira, P.: Sheaves on Manifolds. Springer, Berlin (1990) · Zbl 0709.18001
[35] Mac Lane, S.: Categories for the Working Mathematician, 2nd edn. Springer, Berlin (1998) · Zbl 0906.18001
[36] Mather, J.: Notes on topological stability. Bull. AMS 49(4) (2012) · Zbl 1260.57049
[37] Mendelson, B.: Introduction to Topology. Allyn and Bacon Inc, Newton, MA (1975) · Zbl 0304.54003
[38] Morozov, D., Beketayev, K., Weber, G.: Interleaving distance between merge trees. In: Proceedings of TopoInVis (2013)
[39] Nicolau, M; Levine, AJ; Carlsson, G, Topology based data analysis identifies a subgroup of breast cancers with a unique mutational profile and excellent survival, Proc. Natl. Acad. Sci., 108, 7265-7270, (2011)
[40] Parsa, S.: A deterministic \(O(m \log m)\) time algorithm for the Reeb graph. In: Proceedings of the 28th annual ACM symposium on Computational geometry, SoCG ’12. ACM (2012) · Zbl 1293.05193
[41] Pascucci, V; Cole-McLaughlin, K, Parallel computation of the topology of level sets, Algorithmica, 38, 249-268, (2004) · Zbl 1072.68112
[42] Pascucci, V., Scorzelli, G., Bremer, P.-T., Mascarenhas, A.: Robust on-line computation of Reeb graphs: simplicity and speed. ACM Trans. Graph. 26(3) (2007)
[43] Reeb, G, Sur LES points singuliers d’une forme de Pfaff complèment intégrable ou d’une fonction numérique, C. R. L’Acad. Sci., 222, 847-849, (1946) · Zbl 0063.06453
[44] Shinagawa, Y; Kunii, TL; Kergosien, YL, Surface coding based on Morse theory, IEEE Comput. Graph. Appl., 11, 66-78, (1991)
[45] Singh, G., Mémoli, F., Carlsson, G.: Topological methods for the analysis of high dimensional data sets and 3D object recognition. In: Eurographics Symposium on Point-Based Graphics (2007)
[46] Sleator, DD; Tarjan, RE, A data structure for dynamic trees, J. Comput. Syst. Sci., 26, 362-391, (1983) · Zbl 0509.68058
[47] Sleator, DD; Tarjan, RE, Self-adjusting binary search trees, J. ACM, 32, 652-686, (1985) · Zbl 0631.68060
[48] Szymczak, A; Pascucci, V (ed.); Tricoche, H (ed.); Hagen, H (ed.); Tierny, J (ed.), A categorical approach to contour, split and join trees with application to airway segmentation, 205-216, (2011), Berlin · Zbl 1214.68451
[49] Tarjan, R.E., Werneck, R.F.: Self-adjusting top trees. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’05, pp. 813-822. Society for Industrial and Applied Mathematics, Philadelphia, PA (2005) · Zbl 1297.68069
[50] Treumann, D, Exit paths and constructible stacks, Compos. Math., 145, 1504-1532, (2009) · Zbl 1185.32022
[51] Tucker, AW, Branched and folded coverings, Bull. Am. Math. Soc, 42, 859-862, (1936) · Zbl 0015.37505
[52] van den Dries, L.: Tame Topology and O-minimal Structures. London Mathematical Society Lecture Note Series, vol. 248. Cambridge University Press, Cambridge (1998) · Zbl 0953.03045
[53] van Kreveld, M., van Oostrum, R., Bajaj, C., Pascucci, V., Schikore, D.: Contour trees and small seed sets for isosurface traversal. In: Proceedings of the Thirteenth Annual Symposium on Computational Geometry, SoCG ’97, pp. 212-220. ACM, New York, NY (1997)
[54] Weber, GH; Bremer, P-T; Pascucci, V, Topological landscapes: a terrain metaphor for scientific data, IEEE Trans. Vis. Comput. Graph., 13, 1416-1423, (2007)
[55] Wood, Z; Hoppe, H; Desbrun, M; Schröder, P, Removing excess topology from isosurfaces, ACM Trans. Graph., 23, 190-208, (2004)
[56] Woolf, J, The fundamental category of a stratified space, J. Homotopy Relat. Struct., 4, 359-387, (2009) · Zbl 1204.18008
[57] Yao, Y; Sun, J; Huang, X; Bowman, GR; Singh, G; Lesnick, M; Guibas, LJ; Pande, VS; Carlsson, G, Topological methods for exploring low-density states in biomolecular folding pathways, J. Chem. Phys., 130, 144115, (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.