Learning and triangulating manifolds via collapses

Computers are digital or discrete, while shapes in our world are smooth or at least continuous. To use the computer, we need to go from a smooth to a digital description of the world. This is not difficult in 2D, think of Pac-Man, but it becomes difficult already in 3D. In the last few decades, great progress has been made on this front; compare, for example, Shogun: Total War or Super Mario 64 with modern games like Forza Horizon 4 and Red Dead Redemption 2 or films like Interstellar. While we think of the world around us as 3D, the story does not end here. For example, black holes are modelled by Einstein`s theory of general relativity in 4D, integrating space and time into spacetime. The corresponding computations are also 4D, in particular the gas flowing into the black hole. Dimensions beyond 3D are not only important for general relativity: - In data science high, dimensions occur easily: to keep track of how much money people spend each month in a year on food, drinks, clothes, video games and the cinema gives you a point in (5 times 12 equals) 60 dimensional space per person. - Robots with several joints give rise to trajectories in high dimensions because each angle that a joint makes with a adjacent joint adds one dimensions. - High-dimensional spaces also occur when we model the flow of gas around air plane wings, or when we study the position of individual atoms in a molecule. In the next two years we will develop new, provably correct, and fast algorithms to discretize spaces beyond 3 dimensions. There are already some algorithms for this, but they are either slow or you don`t know if the output is correct and sometimes both. We are in the early stages of the development of high-dimensional discretization methods, like 3D-graphics was in the 80s and 90s of the last century, and we expect strong developments that mirror the advances in 3D graphics.

The medial axis is a set that lies in the middle of a shape and acts as a skeleton. For example if one considers the contour of a hand in the plane then the medial axis is a tree-like structure for which every branch corresponds to a finger. Using the medial axis it is easy to distinguish different components (in this case fingers) of a geometric shape. It also encodes some of the geometry of a shape. It is therefore often used in shape segmentation, shape learning, and shape recognition. The goal of shape segmentation is for a computer to automatically identify different parts of shape, such as fingers in our example above. However, in spite of it being quite useful in practice, it has significant problems: In practice we don't have a mathematically perfect geometric shape. We can only measure a shape with some finite precision, to put it differently there is some noise in the measurement. Moreover, we can only perform a finite number of measurements. However, it is well known that even a little bit of noise can change the medial axis dramatically. This instability is so profound that it was not proven that one can calculate the medial axis using a so-called Turing machine. A Turing machine is a model for a `perfect' computer, introduced by the founder of computer science and WW2 code breaking hero Alan Turing (known to the general public thanks to the film `The Imitation Game'). We (that is collaborators and I) addressed the instability of the medial axis during the last couple of years. We showed that the medial axis becomes stable with the right changes (pruning), which also implies that it is computable with a Turing Machine. On the practical side, our result implies that the medial axis is a reliable tool for shape segmentation and shape learning, i.e. even with noisy data one can find (a good approximation of) the medial axis, which then can be used in learning or segmentation algorithms. This project contributed in a small way to the search for explainable artificial intelligence and explainable machine learning: In the last decades computer scientists have achieved impressive results using deep neural networks. However, the problem with most learning based on neural networks is that it cannot explain the answers it gives and sometimes the results are completely wrong. This problem occurs in most branches of machine learning, not only deep learning. For the medial axis of a geometric shape this project has gone one step beyond explainable machine learning: We have proven that the medial axis can be well approximated, mathematically underpinning a large number of learning algorithms based on the medial axis.