The Morse theory of Čech and Delaunay complexes
HTML articles powered by AMS MathViewer
- by Ulrich Bauer and Herbert Edelsbrunner PDF
- Trans. Amer. Math. Soc. 369 (2017), 3741-3762 Request permission
Abstract:
Given a finite set of points in $\mathbb {R}^n$ and a radius parameter, we study the Čech, Delaunay–Čech, Delaunay (or alpha), and Wrap complexes in the light of generalized discrete Morse theory. Establishing the Čech and Delaunay complexes as sublevel sets of generalized discrete Morse functions, we prove that the four complexes are simple-homotopy equivalent by a sequence of simplicial collapses, which are explicitly described by a single discrete gradient field.References
- Paul Alexandroff, Simpliziale Approximationen in der allgemeinen Topologie, Math. Ann. 96 (1927), no. 1, 489–511 (German). MR 1512335, DOI 10.1007/BF01209183
- Dominique Attali, André Lieutier, and David Salinas, Vietoris-Rips complexes also provide topologically correct reconstructions of sampled shapes, Comput. Geom. 46 (2013), no. 4, 448–465. MR 3003901, DOI 10.1016/j.comgeo.2012.02.009
- F. Aurenhammer, Power diagrams: properties, algorithms and applications, SIAM J. Comput. 16 (1987), no. 1, 78–96. MR 873251, DOI 10.1137/0216006
- Jonathan Ariel Barmak, On Quillen’s Theorem A for posets, J. Combin. Theory Ser. A 118 (2011), no. 8, 2445–2453. MR 2834186, DOI 10.1016/j.jcta.2011.06.008
- Ulrich Bauer and Herbert Edelsbrunner, The Morse theory of Čech and Delaunay filtrations, Computational geometry (SoCG’14), ACM, New York, 2014, pp. 484–490. MR 3382330
- Ulrich Bauer and Michael Lesnick, Induced matchings and the algebraic stability of persistence barcodes, J. Comput. Geom. 6 (2015), no. 2, 162–191. MR 3333456, DOI 10.20382/jocg.v6i2a9
- Omer Bobrowski and Robert J. Adler, Distance functions, critical points, and the topology of random Čech complexes, Homology Homotopy Appl. 16 (2014), no. 2, 311–344. MR 3280987, DOI 10.4310/HHA.2014.v16.n2.a18
- Karol Borsuk, On the imbedding of systems of compacta in simplicial complexes, Fund. Math. 35 (1948), 217–234. MR 28019, DOI 10.4064/fm-35-1-217-234
- Stephen Boyd and Lieven Vandenberghe, Convex optimization, Cambridge University Press, Cambridge, 2004. MR 2061575, DOI 10.1017/CBO9780511804441
- Kevin Buchin, Tamal K. Dey, Joachim Giesen, and Matthias John, Recursive geometry of the flow complex and topology of the flow complex filtration, Comput. Geom. 40 (2008), no. 2, 115–137. MR 2400538, DOI 10.1016/j.comgeo.2007.05.005
- Gunnar Carlsson, Topology and data, Bull. Amer. Math. Soc. (N.S.) 46 (2009), no. 2, 255–308. MR 2476414, DOI 10.1090/S0273-0979-09-01249-X
- F. Cazals, A. Parameswaran, and S. Pion, Robust construction of the three-dimensional flow complex, Computational geometry (SCG’08), ACM, New York, 2008, pp. 182–191. MR 2504285, DOI 10.1145/1377676.1377705
- E. Čech, Théorie générale de l’homologie dans un espace quelconque, Fund. Math. 19 (1933), no. 1.
- E. Čech, General homology theory in an arbitrary space, in The Mathematical Legacy of Eduard Čech, M. Katětov and P. Simon, editors, Birkhäuser Basel, 1993, pp. 231–255. Translated from French by J. Vanžura.
- Manoj K. Chari, On discrete Morse functions and combinatorial decompositions, Discrete Math. 217 (2000), no. 1-3, 101–113 (English, with English and French summaries). Formal power series and algebraic combinatorics (Vienna, 1997). MR 1766262, DOI 10.1016/S0012-365X(99)00258-7
- F. Chazal, D. C. Steiner, M. Glisse, L. J. Guibas, and S. Y. Oudot, Proximity of persistence modules and their diagrams, in Proceedings of the Twenty-fifth Annual Symposium on Computational Geometry, SCG ’09, ACM, New York, NY, USA, 2009, pp. 237–246.
- Harish Kumar Chintakunta, Topology and Geometry of Sensor Networks: A Distributed Computing Approach, ProQuest LLC, Ann Arbor, MI, 2013. Thesis (Ph.D.)–North Carolina State University. MR 3211268
- Marshall M. Cohen, A course in simple-homotopy theory, Graduate Texts in Mathematics, Vol. 10, Springer-Verlag, New York-Berlin, 1973. MR 0362320
- V. de Silva and G. Carlsson, Topological estimation using witness complexes, in Symposium on Point-Based Graphics (SPBG) 2004, M. Gross, H. Pfister, M. Alexa, and S. Rusinkiewicz, editors, The Eurographics Association, 2004.
- Tamal K. Dey, Herbert Edelsbrunner, and Sumanta Guha, Computational topology, Advances in discrete and computational geometry (South Hadley, MA, 1996) Contemp. Math., vol. 223, Amer. Math. Soc., Providence, RI, 1999, pp. 109–143. MR 1661380, DOI 10.1090/conm/223/03135
- Rex A. Dwyer, Higher-dimensional Voronoĭ diagrams in linear expected time, Discrete Comput. Geom. 6 (1991), no. 4, 343–367. MR 1098813, DOI 10.1007/BF02574694
- H. Edelsbrunner, Alpha shapes — a survey, in Tessellations in the Sciences: Virtues, Techniques and Applications of Geometric Tilings, R. van de Weygaert, G. Vegter, J. Ritzerveld, and V. Icke, editors, Springer Verlag, to appear.
- H. Edelsbrunner, The union of balls and its dual shape, Discrete Comput. Geom. 13 (1995), no. 3-4, 415–440. MR 1318786, DOI 10.1007/BF02574053
- Herbert Edelsbrunner, Surface reconstruction by wrapping finite sets in space, Discrete and computational geometry, Algorithms Combin., vol. 25, Springer, Berlin, 2003, pp. 379–404. MR 2038483, DOI 10.1007/978-3-642-55566-4_{1}7
- Herbert Edelsbrunner and John L. Harer, Computational topology, American Mathematical Society, Providence, RI, 2010. An introduction. MR 2572029, DOI 10.1090/mbk/069
- Herbert Edelsbrunner, David G. Kirkpatrick, and Raimund Seidel, On the shape of a set of points in the plane, IEEE Trans. Inform. Theory 29 (1983), no. 4, 551–559. MR 713690, DOI 10.1109/TIT.1983.1056714
- Robin Forman, Morse theory for cell complexes, Adv. Math. 134 (1998), no. 1, 90–145. MR 1612391, DOI 10.1006/aima.1997.1650
- Ragnar Freij, Equivariant discrete Morse theory, Discrete Math. 309 (2009), no. 12, 3821–3829. MR 2537376, DOI 10.1016/j.disc.2008.10.029
- I. M. Gel′fand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1264417, DOI 10.1007/978-0-8176-4771-1
- Joachim Giesen and Matthias John, The flow complex: a data structure for geometric modeling, Comput. Geom. 39 (2008), no. 3, 178–190. MR 2381026, DOI 10.1016/j.comgeo.2007.01.002
- Patricia Hersh, On optimizing discrete Morse functions, Adv. in Appl. Math. 35 (2005), no. 3, 294–322. MR 2164921, DOI 10.1016/j.aam.2005.04.001
- Jakob Jonsson, Simplicial complexes of graphs, Lecture Notes in Mathematics, vol. 1928, Springer-Verlag, Berlin, 2008. MR 2368284, DOI 10.1007/978-3-540-75859-4
- Matthew Kahle, Random geometric complexes, Discrete Comput. Geom. 45 (2011), no. 3, 553–573. MR 2770552, DOI 10.1007/s00454-010-9319-3
- A. Lieutier, Any open bounded subset of $\mathbb R^n$ has the same homotopy type as its medial axis, Computer-Aided Design 36 (2004), no. 11, 1029–1046.
- P. McMullen, The maximum numbers of faces of a convex polytope, Mathematika 17 (1970), 179–184. MR 283691, DOI 10.1112/S0025579300002850
- F. T. Pokorny, M. Hawasly, and S. Ramamoorthy Topological trajectory classification with filtrations of simplicial complexes and persistent homology, The International Journal of Robotics Research 35 (2016), nos. 1-3, 204–223.
- Raimund Seidel, The upper bound theorem for polytopes: an easy proof of its asymptotic version, Comput. Geom. 5 (1995), no. 2, 115–116. MR 1353291, DOI 10.1016/0925-7721(95)00013-Y
- D. Siersma, Voronoi diagrams and Morse theory of the distance function, in Geometry in Present Day Science, World Scientific, 1999, pp. 187–208.
- M. van Manen and D. Siersma, Power diagrams and Morse theory, Preprint, Apr. 2014.
- L. Vietoris, Über den höheren Zusammenhang kompakter Räume und eine Klasse von zusammenhangstreuen Abbildungen, Math. Ann. 97 (1927), no. 1, 454–472 (German). MR 1512371, DOI 10.1007/BF01447877
- Gerd Wegner, $d$-collapsing and nerves of families of convex sets, Arch. Math. (Basel) 26 (1975), 317–321. MR 375333, DOI 10.1007/BF01229745
Additional Information
- Ulrich Bauer
- Affiliation: Department of Mathematics, Technical University of Munich, 85748 Garching, Germany
- MR Author ID: 898087
- Email: ulrich-bauer.org
- Herbert Edelsbrunner
- Affiliation: Department of Computer Science, University of Illinois, Urbana, Illinois 61801
- Address at time of publication: IST Austria, 3400 Klosterneuburg, Austria
- MR Author ID: 61770
- Email: edels@ist.ac.at
- Received by editor(s): August 11, 2015
- Received by editor(s) in revised form: April 15, 2016, and May 31, 2016
- Published electronically: December 27, 2016
- © Copyright 2016 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 369 (2017), 3741-3762
- MSC (2010): Primary 52C99; Secondary 51F99, 55U10, 57Q10
- DOI: https://doi.org/10.1090/tran/6991
- MathSciNet review: 3605986