Ulrich Bauer

I am an assistant professor in the Geometry & Visualization group at TUM. I did my PhD with Max Wardetzky in the research group Discrete Differential Geometry at the University of Göttingen and a postdoc in Herbert Edelsbrunner's research group at IST Austria.

Research interests:

Discrete/Computational Geometry/Topology, Algorithms, Combinatorics.


Prof. Dr. Ulrich Bauer
Geometrie & Visualisierung (M10)
Fakultät für Mathematik
Technische Universität München
Boltzmannstraße 3
D-85747 Garching bei München
Vox: +49 89 289 18361
Net: mail (at) ulrich-bauer.org

Persistent Homology meets Statistical Inference - A Case Study: Detecting Modes of One-Dimensional Signals
Ulrich Bauer, Axel Munk, Hannes Sieling, and Max Wardetzky. Preprint, 2014.
Abstract: We investigate the problem of estimating persistent homology of noisy one dimensional signals. We relate this to the problem of estimating the number of modes (i.e., local maxima) – a well known question in statistical inference -- and we show how to do so without presmoothing the data. To this end, we extend the ideas of persistent homology by working with norms different from the (classical) supremum norm. As a particular case we investigate the so called Kolmogorov norm. We argue that this extension has certain statistical advantages. We offer confidence bands for the attendant Kolmogorov signatures, thereby allowing for the selection of relevant signatures with a statistically controllable error. As a result of independent interest, we show that so-called taut strings minimize the number of critical points for a very general class of functions. We illustrate our results by several numerical examples.

The Morse theory of Čech and Delaunay filtrations
Ulrich Bauer and Herbert Edelsbrunner. SoCG '14 Proceedings of the twenty-ninth annual symposium on Computational geometry (2014), 484–490.
Abstract: Given a finite set of points in ℝⁿ and a positive radius, we consider the Čech, Delaunay–Čech, alpha, and wrap complexes as examples of a generalized discrete Morse theory. We prove that the latter three are simple-homotopy equivalent, and the same is true for their weighted versions. Our results have applications in topological data analysis and in the reconstruction of shapes from sampled data.
[pdf] [doi] [arXiv]

Induced Matchings of Barcodes and the Algebraic Stability of Persistence
Ulrich Bauer and Michael Lesnick. SoCG '14 Proceedings of the twenty-ninth annual symposium on Computational geometry (2014), 355–364. Invited to special issue of Journal of Computational Geometry.
Abstract: We define a simple, explicit map sending a morphism f: M → N of pointwise finite dimensional persistence modules to a matching between the barcodes of M and N. Our main result is that, in a precise sense, the quality of this matching is tightly controlled by the lengths of the longest intervals in the barcodes of ker f and coker f. As an immediate corollary, we obtain a new proof of the algebraic stability of persistence, a fundamental result in the theory of persistent homology. In contrast to previous proofs, ours shows explicitly how a δ-interleaving morphism between two persistence modules induces a δ-matching between the barcodes of the two modules. Our main result also specializes to a structure theorem for submodules and quotients of persistence modules.
[pdf] [doi] [arXiv]

Measuring Distance between Reeb Graphs
Ulrich Bauer, Xiaoyin Ge, and Yusu Wang. SoCG '14 Proceedings of the twenty-ninth annual symposium on Computational geometry (2014), 464–473.
Abstract: We propose a metric for Reeb graphs, called the functional distortion distance. Under this distance measure, the Reeb graph is stable against small changes of input functions. At the same time, it remains discriminative at differentiating input functions. In particular, the main result is that the functional distortion distance between two Reeb graphs is bounded from below by (and thus more discriminative than) the bottleneck distance between both the ordinary and extended persistence diagrams for appropriate dimensions.
As an application of our results, we analyze a natural simplification scheme for Reeb graphs, and show that persistent features in Reeb graph remains persistent under simplification. Understanding the stability of important features of the Reeb graph under simplification is an interesting problem on its own right, and critical to the practical usage of Reeb graphs.
[pdf] [doi] [arXiv]

Clear and Compress: Computing Persistent Homology in Chunks
Ulrich Bauer, Michael Kerber, and Jan Reininghaus, Topological Methods in Data Analysis and Visualization III Mathematics and Visualization 2014, 103–117.
Abstract: We present a parallelizable algorithm for computing the persistent homology of a filtered chain complex. Our approach differs from the commonly used reduction algorithm by first computing persistence pairs within local chunks, then simplifying the unpaired columns, and finally applying standard reduction on the simplified matrix. The approach generalizes a technique by Günther et al., which uses discrete Morse Theory to compute persistence; we derive the same worst-case complexity bound in a more general context. The algorithm employs several practical optimization techniques which are of independent interest. Our sequential implementation of the algorithm is competitive with state-of-the-art methods, and we improve the performance through parallelized computation.
[doi] [arXiv]

Distributed computation of persistent homology
Ulrich Bauer, Michael Kerber, and Jan Reininghaus. Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX14), 31–38.
Abstract: Persistent homology is a popular and powerful tool for capturing topological features of data. Advances in algorithms for computing persistent homology have reduced the computation time drastically – as long as the algorithm does not exhaust the available memory. Following up on a recently presented parallel method for persistence computation on shared memory systems, we demonstrate that a simple adaption of the standard reduction algorithm leads to a variant for distributed systems. Our algorithmic design ensures that the data is distributed over the nodes without redundancy; this permits the computation of much larger instances than on a single machine. Moreover, we observe that the parallelism at least compensates for the overhead caused by communication between nodes, and often even speeds up the computation compared to sequential and even parallel shared memory algorithms. In our experiments, we were able to compute the persistent homology of filtrations with more than a billion (10⁹) elements within seconds on a cluster with 32 nodes using less than 10GB of memory per node.
[pdf] [doi]

Homological reconstruction and simplification in R³
Dominique Attali, Ulrich Bauer, Olivier Devillers, Marc Glisse, and André Lieutier. SoCG '13 Proceedings of the twenty-ninth annual symposium on Computational geometry (2013), 117–126.
Accepted for special issue of Computation Geometry: Theory and Applications.
Abstract: We consider the problem of deciding whether the persistent homology group of a simplicial pair (K,L) can be realized as the homology H*(X) of some complex X with L ⊂ X ⊂ K. We show that this problem is NP-complete even if K is embedded in R³. As a consequence, we show that it is NP-hard to simplify level and sublevel sets of scalar functions on S³ within a given tolerance constraint. This problem has relevance to the visualization of medical images by isosurfaces. We also show an implication to the theory of well groups of scalar functions: not every well group can be realized by some level set, and deciding whether a well group can be realized is NP-hard.
[pdf] [doi]

Optimal topological simplification of discrete functions on surfaces
Ulrich Bauer, Carsten Lange, and Max Wardetzky. Discrete and Computational Geometry 47:2 (2012), 347–377.
Abstract: Given a function f on a surface and a tolerance δ > 0, we construct a function fδ subject to ‖fδ - f‖ ≤ δ such that fδ has a minimum number of critical points. Our construction relies on a connection between discrete Morse theory and persistent homology and completely removes homological noise with persistence ≤ 2δ from the input function f. The number of critical points of the resulting simplified function fδ achieves the lower bound dictated by the stability theorem of persistent homology. We show that the simplified function can be computed in linear time after persistence pairs have been computed.
[pdf] [doi]

Persistence in discrete Morse Theory
PhD thesis, University of Göttingen, 2011.

[pdf] [hdl]

Total Variation Meets Topological Persistence: A First Encounter
Ulrich Bauer, Carola-Bibiane Schönlieb, and Max Wardetzky. Proceedings of ICNAAM 2010, 1022–1026.
Abstract: We present first insights into the relation between two popular yet apparently dissimilar approaches to denoising of one dimensional signals, based on (i) total variation (TV) minimization and (ii) ideas from topological persistence. While a close relation between (i) and (ii) might phenomenologically not be unexpected, our work appears to be the first to make this connection precise for one dimensional signals. We provide a link between (i) and (ii) that builds on the equivalence between TV-L2 regularization and taut strings and leads to a novel and efficient denoising algorithm that is contrast preserving and operates in O(nlogn) time, where n is the size of the input.
[pdf] [doi]

curvature lines
Uniform Convergence of Discrete Curvatures from Nets of Curvature Lines
Ulrich Bauer, Konrad Polthier, Max Wardetzky, Discrete and Computational Geometry 43:4 (2010), 798–823.
Abstract: We study “Steiner-type” discrete curvatures computed from nets of curvature lines on a given smooth surface, and prove their uniform pointwise convergence to smooth principal curvatures. We provide explicit error bounds, with constants depending only on the limit surface and the shape regularity of the discrete net.
[pdf] [doi]

Generating Parametric Models of Tubes from Laser Scans
Ulrich Bauer, Konrad Polthier, Computer-Aided Design 41 (2009), 719–729.
Conference version: Parametric Reconstruction of Bent Tube Surfaces, Proceedings NASAGEM/Cyberworlds 2007, 465–474. [pdf] [doi]
Abstract: We present a method for parametric reconstruction of a piecewise defined pipe surface, consisting of cylinder and torus segments, from an unorganized point set. Our main contributions are reconstruction of the spine curve of a pipe surface from surface samples, and approximation of the spine curve by continuous circular arcs and line segments. Our algorithm accurately outputs the parametric data required for bending machines to create the reconstructed tube.
[pdf] [doi]

plane detection
Detection of Planar Regions in Volume Data for Topology Optimization
Ulrich Bauer, Konrad Polthier, Proceedings of Geometry Modelling and Processing 2008, Lecture Notes in Computer Science vol. 4975 (2008), 119–126.
Abstract: We propose a method to identify planar regions in volume data using a specialized version of the discrete Radon transform operating on a structured or unstructured grid. The algorithm uses an efficient discretization scheme for the parameter space to obtain a running time of O(N(T log T)), where T is the number of cells and N is the number of plane normals in the discretized parameter space. We apply our algorithm in an industrial setting and perform experiments with real-world data generated by topology optimization algorithms, where the planar regions represent portions of a mechanical part that can be built using steel plate.
[pdf] [doi]

Undergraduate projects

Assignment Problem with Constraints
Diploma Thesis – ETH Zürich (10/2004 – 03/2005)
Abstract: Combinatorial optimisation plays an important role in logistics, and many of the basic problems and algorithms find a direct application in this area or even originate from it. For instance, the assignment problem asks for a cost-optimal assignment of workers to tasks or products to warehouse locations.
Additional constraints on the solutions, such as an equal distribution of products to warehouses, are however often required in real-world settings. An algorithm to solve this problem is developed based on Bertsekas' well-known auction algorithm.
Advisors: Andreas Weissl and Prof. Angelika Steger, ETH Zürich

Minimum Cycle Bases Algorithms for the Chemistry Development Kit

Interdisciplinary project – TU München (04/2004 – 09/2004)

The cycles of a graph (the subgraphs whose vertices have even degree) span a matroid; addition on this matroid is defined as the symmetric difference of the edges. A cycle basis is a maximal set of linearly independent cycles; a minimum cycle basis is a cycle basis with minimum edge count (or minimum total edge weight in the case of weighted graphs).
The Smallest Set of Smallest Rings (SSSR), the chemical equivalent to a minimum cycle basis, plays an important role in computational chemistry. However, an efficient and exact algorithm for computing an SSSR was missing from the Chemistry Development Toolkit (CDK), a comprehensive library for computational chemistry which is used in several projects such as JMol and JChemPaint.
We present details about the implementation of several algorithms related to minimum cycles bases and provide several improvements to the algorithms that lower the computational complexity of the minimum cycle basis algorithm to O(m³).
Advisors: Franziska Berger and Prof. Peter Gritzmann, TU München

Hydra: Collaborative Text Editor

Application development – TU München (01/2003 – 06/2003)

Hydra is an easy-to-use collaborative real-time text editor for Mac OS X. It uses operational transformations to synchronise text on the different participating computers and allows users to simultaneously edit a text file without locking.
Hydra has won several awards, among them the Apple Design Award and the O'Reilly Mac OS X Innovators Award. It is now a commercial product maintained by two of my co-authors under the name SubEthaEdit.
Apple Design Award O'Reilly Mac OS X Innovators Award


That's me