The Morse theory of Čech and Delaunay complexes

Bauer, Ulrich; Edelsbrunner, Herbert

doi:10.1090/tran/6991

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