Algorithms for Embeddings and Homotopy Theory

The mathematical field of topology studies geometric shapes (`topological spaces`), in particular those properties of shapes that do not change if we continuously deform the shape (i.e., we are allowed to stretch, bend, and twist the shape, but not to tear it or to perforate it). A classical example of such a property is the question whether a shape is simply connected, i.e., whether every closed loop in a given shape can be contracted to a point within the shape (the loop is allowed to pass through itself, but not to leave the shape)for example, a 2-dimensional sphere is simply connected, but a torus (the surface of a doughnut) is not. Computational topology studies the question for which topological properties of shapes can, in principle be tested by an algorithm. For example, it is a classical result that there is no algorithm that can correctly decide for any given geometric shape whether the shape is simply connected or not. (For these algorithmic problems, we assume that the geometric shapes in question are described in a way that can be used as input for an algorithm, for instance as a simplicial complexa set of instructions how to build the shape from simple building blocks like triangles and tetrahedra.) The present project studies two topological problems: the first is, whether a given geometric shape can be embedded (possibly twisted and bent but without intersecting itself) into ambient three- or higher-dimensional space; the second topic are higher-dimensional generalizations of simple connectivity (e.g., so-called homotopy groups). The goal is to find out under which conditions these questions and properties can be decided algorithmically (or not) and which resources (time and memory) are, in principle, necessary. A further, related goal is to quantify the geometric complexity of embeddings and homotopies, e.g., to understand how much, in the worst case, a shape needs to be twisted, distorted, or folded in order to embed it.

A simplicial complex is a description how to build a geometric shape (a "topological space") by glueing together simple building blocks--segments, triangles, tetrahedra, and their higher-dimensional generalizations, simplices. Given a geometric shape described in this way, can it be embedded (possibly stretched and contorted, but without self-intersections) into 3-dimensional space? What if we replace our familiar 3-dimensional space by d-dimensional space? In this project, we investigate this and various related classical problems from geometry and topology from a point of view of algorithms and computational complexity. We show that some of these questions are solvable by efficient (polynomial-time) algorithms, while others are in principle (and mathematically provably) algorithmically unsolvable. Interestingly, our methods also allow us to prove results that, at first sight, have nothing to do with higher dimensions, such as the following: For every positive integer n, every convex region in the plane can be partitioned into n convex regions of equal area and equal diameter. (Here, a region is convex if, along with any two points, it contains the entire line segment connecting the two points.)