Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

The Morse theory of Čech and Delaunay complexes


Authors: Ulrich Bauer and Herbert Edelsbrunner
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
Published electronically: December 27, 2016
MathSciNet review: 3605986
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Paul Alexandroff, Simpliziale Approximationen in der allgemeinen Topologie, Math. Ann. 96 (1927), no. 1, 489-511 (German). MR 1512335, https://doi.org/10.1007/BF01209183
  • [2] 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, https://doi.org/10.1016/j.comgeo.2012.02.009
  • [3] F. Aurenhammer, Power diagrams: properties, algorithms and applications, SIAM J. Comput. 16 (1987), no. 1, 78-96. MR 873251, https://doi.org/10.1137/0216006
  • [4] Jonathan Ariel Barmak, On Quillen's Theorem A for posets, J. Combin. Theory Ser. A 118 (2011), no. 8, 2445-2453. MR 2834186, https://doi.org/10.1016/j.jcta.2011.06.008
  • [5] 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
  • [6] 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
  • [7] 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, https://doi.org/10.4310/HHA.2014.v16.n2.a18
  • [8] Karol Borsuk, On the imbedding of systems of compacta in simplicial complexes, Fund. Math. 35 (1948), 217-234. MR 0028019
  • [9] Stephen Boyd and Lieven Vandenberghe, Convex optimization, Cambridge University Press, Cambridge, 2004. MR 2061575
  • [10] 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, https://doi.org/10.1016/j.comgeo.2007.05.005
  • [11] Gunnar Carlsson, Topology and data, Bull. Amer. Math. Soc. (N.S.) 46 (2009), no. 2, 255-308. MR 2476414, https://doi.org/10.1090/S0273-0979-09-01249-X
  • [12] 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, https://doi.org/10.1145/1377676.1377705
  • [13] E. Čech, Théorie générale de l'homologie dans un espace quelconque, Fund. Math. 19 (1933), no. 1.
  • [14] 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.
  • [15] 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). MR 1766262, https://doi.org/10.1016/S0012-365X(99)00258-7
  • [16] 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.
  • [17] 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
  • [18] Marshall M. Cohen, A course in simple-homotopy theory, Graduate Texts in Mathematics, vol. 10, Springer-Verlag, New York-Berlin, 1973. MR 0362320
  • [19] 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.
  • [20] 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, https://doi.org/10.1090/conm/223/03135
  • [21] Rex A. Dwyer, Higher-dimensional Voronoĭ diagrams in linear expected time, Discrete Comput. Geom. 6 (1991), no. 4, 343-367. MR 1098813, https://doi.org/10.1007/BF02574694
  • [22] 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.
  • [23] H. Edelsbrunner, The union of balls and its dual shape, Discrete Comput. Geom. 13 (1995), no. 3-4, 415-440. MR 1318786, https://doi.org/10.1007/BF02574053
  • [24] 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, https://doi.org/10.1007/978-3-642-55566-4_17
  • [25] Herbert Edelsbrunner and John L. Harer, Computational topology: An introduction, American Mathematical Society, Providence, RI, 2010. MR 2572029
  • [26] 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, https://doi.org/10.1109/TIT.1983.1056714
  • [27] Robin Forman, Morse theory for cell complexes, Adv. Math. 134 (1998), no. 1, 90-145. MR 1612391, https://doi.org/10.1006/aima.1997.1650
  • [28] Ragnar Freij, Equivariant discrete Morse theory, Discrete Math. 309 (2009), no. 12, 3821-3829. MR 2537376, https://doi.org/10.1016/j.disc.2008.10.029
  • [29] I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1264417
  • [30] Joachim Giesen and Matthias John, The flow complex: a data structure for geometric modeling, Comput. Geom. 39 (2008), no. 3, 178-190. MR 2381026, https://doi.org/10.1016/j.comgeo.2007.01.002
  • [31] Patricia Hersh, On optimizing discrete Morse functions, Adv. in Appl. Math. 35 (2005), no. 3, 294-322. MR 2164921, https://doi.org/10.1016/j.aam.2005.04.001
  • [32] Jakob Jonsson, Simplicial complexes of graphs, Lecture Notes in Mathematics, vol. 1928, Springer-Verlag, Berlin, 2008. MR 2368284
  • [33] Matthew Kahle, Random geometric complexes, Discrete Comput. Geom. 45 (2011), no. 3, 553-573. MR 2770552, https://doi.org/10.1007/s00454-010-9319-3
  • [34] 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.
  • [35] P. McMullen, The maximum numbers of faces of a convex polytope, Mathematika 17 (1970), 179-184. MR 0283691
  • [36] 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.
  • [37] 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, https://doi.org/10.1016/0925-7721(95)00013-Y
  • [38] D. Siersma, Voronoi diagrams and Morse theory of the distance function, in Geometry in Present Day Science, World Scientific, 1999, pp. 187-208.
  • [39] M. van Manen and D. Siersma, Power diagrams and Morse theory, Preprint, Apr. 2014.
  • [40] 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, https://doi.org/10.1007/BF01447877
  • [41] Gerd Wegner, $ d$-collapsing and nerves of families of convex sets, Arch. Math. (Basel) 26 (1975), 317-321. MR 0375333

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 52C99, 51F99, 55U10, 57Q10

Retrieve articles in all journals with MSC (2010): 52C99, 51F99, 55U10, 57Q10


Additional Information

Ulrich Bauer
Affiliation: Department of Mathematics, Technical University of Munich, 85748 Garching, Germany
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
Email: edels@ist.ac.at

DOI: https://doi.org/10.1090/tran/6991
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
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society