Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Mittagsseminar Talk Information

Date and Time: Tuesday, June 12, 2012, 12:15 pm

Duration: 30 minutes

Location: HG D5.2

Speaker: Andrea Roth (INRIA Sophia-Antipolis)

On Discrete Morse-Smale Decompositions and Bifurcations Diagrams

In the realm of differential topology, Morse theory provides a powerful framework to study the topology of a manifold from a function defined on it. But the smooth concepts do not easily translate in the discrete setting, so that defining critical points and (un-)stable manifolds remains a challenge for functions sampled over a discrete domain, be it a point set or simplicial complex.

Consider the problem of approximating the Morse-Smale (MS) complex of a function sampled on a manifold. Practically, we assume that a point cloud is given, from which a nearest neighbor graph is inferred. We present novel concepts of (selected) critical points (of any index) together with the associated (un-)stable manifolds. These concepts aim at approximating thickened versions of the (un-)stable manifolds, and thus depart from strategies merely mimicking the smooth setting.

We believe that our approach will prove useful for a variety of applications including geometry processing, computational topology, scientific computing (study of vector fields in general), gradient-free non-convex optimization, and molecular modeling.On the theoretical side, we introduce the multi-scale landscape analysis (MLA) framework, an effective version of Morse theory for sampled spaces, aiming at identifying (selected) critical points of any index together with the associated (un-)stable manifolds. Our constructions approximate thickened versions of the (un-)stable manifolds of the critical points, and thus depart from strategies merely mimicking the smooth setting. We further show how topological persistence, a body of methods from computational topology, can be used to single out the most prominent critical points.

On the experimental side, illustrations will be provided on usual non-convex multivariate functions used as benchmark in optimization, and also on polynomial energy landscapes whose critical points can be certified using real algebraic geometry tools.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login