×

Certified computation of planar Morse-Smale complexes. (English) Zbl 1346.65007

Summary: The Morse-Smale complex is an important tool for global topological analysis in various problems of computational geometry and topology. Algorithms for Morse-Smale complexes have been presented in case of piecewise linear manifolds. However, previous research in this field is incomplete in the case of smooth functions. In the current paper we address the following question: Given an arbitrarily complex Morse-Smale system on a planar domain, is it possible to compute its certified (topologically correct) Morse-Smale complex? Towards this, we develop an algorithm using interval arithmetic to compute certified critical points and separatrices forming the Morse-Smale complexes of smooth functions on bounded planar domain. Our algorithm can also compute geometrically close Morse-Smale complexes.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Arnol’d, V., Ordinary Differential Equations, Universitext (2006), Springer-Verlag: Springer-Verlag New York, Heidelberg, Berlin
[2] Bajaj, C.; Schikore, D., Topology preserving data simplification with error bounds, Comput. Graph., 22, 1, 3-12 (1998)
[3] Banchoff, T. F., Critical points and curvature for embedded polyhedral surfaces, Am. Math. Mon., 77, 475-485 (1970) · Zbl 0191.52801
[4] Biasotti, S.; Floriani, L. D.; Falcidieno, B.; Frosini, P.; Giorgi, D.; Landi, C.; Papaleo, L.; Spagnuolo, M., Describing shapes by geometrical-topological properties of real functions, ACM Comput. Surv., 40, 4, 12.1-12.87 (2008)
[6] Cazals, F.; Chazal, F.; Lewiner, T., Molecular Shape Analysis based upon the Morse-Smale Complex and the Connolly Function, (Proceedings of the 19th ACM Symposium on Computational Geometry (2003), ACM Press: ACM Press New York, NY), 351-360 · Zbl 1377.92029
[7] Chattopadhyay, A.; Vegter, G.; Yap, C., Certified Computation of Planar Morse-Smale Complexes, (Proceedings of the 27th ACM Symposium on Computational Geometry (2012), Chapel Hill), 259-268 · Zbl 1293.68301
[8] Chow, S.-N.; Hale, J., Methods of Bifurcation Theory, Grundlehren der mathematischen Wissenschaften, vol. 251 (1982), Springer-Verlag: Springer-Verlag New York, Heidelberg, Berlin
[9] Coddington, E.; Levinson, N., Theory of Ordinary Differential Equations (1955), McGraw-Hill Book Company · Zbl 0064.33002
[10] Edelsbrunner, H.; Harer, J.; Natarajan, V.; Pascucci, V., Morse-Smale complexes for piecewise linear 3-manifolds, (Proc. 19th Ann. Sympos. Comput. Geom. (2003)), 361-370 · Zbl 1375.68125
[11] Edelsbrunner, H.; Harer, J.; Zomorodian, A., Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds, Discrete Comput. Geom., 30, 87-107 (2003) · Zbl 1029.57023
[12] Forman, R., Morse theory for cell complexes, Adv. Math., 134, 90-145 (1998) · Zbl 0896.57023
[13] Gyulassy, A.; Bremer, P.; Hamann, B.; Pascucci, V., A practical approach to Morse-Smale complex computation, IEEE Trans. Vis. Comput., 14, 1619-1626 (2008)
[14] Helman, J. L.; Hesselink, L., Visualizing vector field topology in fluid flows, IEEE Comput. Graph. Appl., 11, 3, 36-46 (1991)
[15] Hirsch, M. W.; Smale, S., Differential Equations, Dynamical Systems, and Linear Algebra (1974), Academic Press · Zbl 0309.34001
[16] Hubbard, J.; West, B., Differential Equations. A Dynamical Systems Approach. Part I, Texts Appl. Math., vol. 5 (1991), Springer Verlag: Springer Verlag New York, Heidelberg, Berlin
[17] Li, C.; Pion, S.; Yap, C., Recent progress in Exact Geometric Computation, J. Log. Algebraic Program., 64, 1, 85-111 (2004), Special issue on “Practical Development of Exact Real Number Computation” · Zbl 1080.68106
[18] Lin, L.; Yap, C., Adaptive isotopic approximation of nonsingular curves: the parameterizability and nonlocal isotopy approach, Discrete Comput. Geom., 45, 4, 760-795 (2011) · Zbl 1221.65048
[19] Meyer, F., Topographic distance and watershed lines, Signal Process., 38, 113-125 (1994) · Zbl 0811.68125
[20] Milnor, J., Morse Theory (1968), Princeton University Press
[21] Moore, R., Interval Analysis (1996), Prentice-Hall
[22] Palis, J.; de Melo, W., Geometric Theory of Dynamical Systems: An Introduction (1982), Springer-Verlag
[23] Plantinga, S.; Vegter, G., Isotopic meshing of implicit surfaces, Vis. Comput., 23, 45-58 (2007)
[24] Snyder, J., Generative Modeling for Computer Graphics and CAD. Symbolic Shape Design Using Interval Analysis (1992), Academic Press Professional, Inc.: Academic Press Professional, Inc. San Diego, CA, USA · Zbl 0759.68089
[25] Snyder, J., Interval analysis for computer graphics, SIGGRAPH Comput. Graph., 26, 2, 121-130 (1992)
[26] Snyder, J. M., Interval analysis for computer graphics, SIGGRAPH Comput. Graph., 26, 2, 121-130 (1992)
[27] Snyder, J. M., Generative Modeling for Computer Graphics and CAD: Symbolic Shape Design Using Interval Analysis (1992), Academic Press Professional, Inc.: Academic Press Professional, Inc. San Diego, CA, USA · Zbl 0759.68089
[28] Takahashi, S.; Ikeda, T.; Shinagawa, Y.; Fujishiro, I., Algorithms for extracting correct critical points and constructing topological graphs from discrete geographic elevation data, Comput. Graph. Forum, 14, 3, 181-192 (1995)
[29] Yap, C., In praise of numerical computation, (Albers, S.; Alt, H.; Näher, S., Efficient Algorithms. Efficient Algorithms, Lecture Notes in Computer Science, vol. 5760 (2009), Springer-Verlag), 308-407, Essays dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday · Zbl 1258.68179
[30] Zhang, E.; Mischaikow, K.; Turk, G., Vector field design on surfaces, ACM Trans. Graph., 25, 4, 1294-1326 (2006)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.