Triangulations in Geometry and Topology

A basic object of study in topology is the $n$–manifold (with boundary): a (second countable and Hausdorff) topological space $M$ which is locally modelled on ${ℝ}^{n-1}\times {ℝ}_{\ge 0}$. The boundary of $M$, denoted $\partial M$, is the subset of points of $M$ which do not have charts in ${ℝ}^n$. We call a manifold $M$ closed if $M$ is compact and $\partial M$ is empty.

As a few simple, but relevant, initial examples we have the $n$–sphere, the $n$–ball, and the $n$–torus:

We write $M\cong N$ if the manifolds $M$ and $N$ are homeomorphic. By invariance of domain if $M\cong N$ then $M$ and $N$ necessarily have the same dimension. Here, then, is the foundational homeomorphism problem:

Note that the homeomorphism problem immediately reduces to the connected case.

Suppose that $N$ is a connected $n$–manifold. We may simplify the homeomorphism problem to the recognition problem:

The recognition problem should, “morally speaking”, be easier than the homeomorphism problem. This is because we may use properties particular to $N$ when constructing our algorithm.

To give a connected manifold $M$ (say, as input to a decision problem) we require a uniform and finitary way to describe it. Note that there are uncountably many homeomorphism types of non-compact $n$–manifolds (for $n\ge 2$); thus, they do not admit finitary descriptions. Accordingly, we henceforth restrict our attention to compact and connected manifolds.

Freedman and Zuddas (2018) prove that compact $n$–manifolds (in the categories TOP, PL, and DIFF) admit uniform and finitary descriptions. The most difficult case occurs in dimension four. To avoid these subtleties, we will restrict our attention to manifolds presented via PL-triangulations. We begin as follows.

Next we give the (necessarily recursive) definition of a PL-triangulation.

All manifolds in dimensions three and below have triangulations, all such triangulations are PL, and any two such PL-triangulations on a single manifold are PL-homeomorphic (Radó 1925 and Moise 1953). On the other hand, work of Freedman, Casson, and Donaldson (and also Kirby-Siebenmann) gives

• $\mathrm{■}$

  four-manifolds that have no triangulation at all and

• $\mathrm{■}$

  four-manifolds that have many distinct PL-structures.

Note, however, that a triangulation of a four-manifold is necessarily a PL-triangulation. ⁶⁶6This relies on the resolution of the three-dimension Poincaré conjecture (Hamilton, Perelman). In dimension five and above the situation is even more complicated.

To avoid these subtle points, we will essentially restrict our attention to the PL category.

Recall our standing hypotheses: the $n$–manifold $M$ is assumed to be connected, compact, and given via a PL-triangulation.

Thus the only zero-manifold allowed is a single point; this has a unique triangulation and so $\text{Homeo}(0)$ has a constant-time solution. The only one-manifold allowed is the circle; so $\text{Homeo}(1)$ amounts to recognising when a finite graph is a cycle. This can be done in polynomial time.

The two-dimensional case is more difficult. By the classification of surfaces a pair of compact, connected two-manifolds are homeomorphic if and only if they

• $\mathrm{■}$

  have the same Euler characteristic,

• $\mathrm{■}$

  have the same number of boundary components, and

• $\mathrm{■}$

  are either both orientable or both non-orientable.

This gives a polynomial-time solution to $\text{Homeo}(2)$.

In higher dimensions (again working in the PL category) there are many negative results.

• $\mathrm{■}$

  For $n\ge 4$ the problem $\text{Homeo}(n)$ is not decidable (Markov 1958).

• $\mathrm{■}$

  For $n\ge 5$ the problem $\text{Recog}(S^n)$ is not decidable (Novikov).

• $\mathrm{■}$

  Thus, in dimensions six and higher, there is no algorithm to decide if a triangulation is PL.

In dimension four there are many well-known, and widely open, algorithmic questions.

This relates to, but would not be answered by, the last remaining part of the Poincaré conjecture: namely, is there a unique smooth (and thus PL) structure on the four-sphere?

This is solved by the trivial algorithm (printing Yes) if the Schoenflies problem has an affirmative answer in dimension four.

Note that the fundamental groups arising from two-knots in the four-sphere are not well understood.

This is closely related to the problem of classifying the PL-structures on a given closed TOP four-manifold.

It is a “folklore result” (Kuperberg, 2019) that the geometrisation theorem (Perelman, 2002-3) implies that $\text{Homeo}(3)$ is decidable. Kuperberg sharpens this result by proving that there is an elementary recursive algorithm (for closed, connected, oriented three-manifolds). Improving this upper bound seems possible.

We suggest approaches to this problem below.

This second question seems much more doubtful. For example, there is a polynomial-time reduction of GraphIso (graph isomorphism) to $\text{Homeo}(3)$ (Lackenby 2022). While GraphIso is now known to be quasi-polynomial time (Babai 2016), it is not yet known to lie in $\mathrm{𝖼𝗈𝖭𝖯}$.

In the other direction, Burton asks for lower bounds.

The three questions above are in tension, due to the standard conjectures in computational complexity. There is evidence that $\text{Homeo}(3)$ is difficult: for example knot genus in arbitrary manifolds is NP-complete (Agol, Hass, Thurston 2006) and various diagrammatic problems for links are NP-complete or NP-hard (Lackenby 2017; Koenig, Tsvietkova 2021). There are other candidate problems which may be $\mathrm{𝖭𝖯}$–complete.

This is known to be decidable (Li 2011) and $\mathrm{𝖭𝖯}$–hard (Bachman, Derby-Talbot, Sedgwick 2017). It seems that showing this lies in $\mathrm{𝖭𝖯}$ requires a delicate control of the normal tori in a triangulation.

Again, this is decidable (Matoušek, Sedgwick, Tancer, Wagner 2018) and $\mathrm{𝖭𝖯}$–hard (de Mesmay, Rieck, Sedgwick, Tancer 2020).

Suppose that $𝒯$ is a triangulation; let $c(𝒯)$ be the number of tetrahedra of $𝒯$. For any compact connected three-manifold $M$ we define its complexity as follows.

The complexity of $M$ is morally similar to, but finer than, the Heegaard genus of $M$.

This problem is decidable, because $\text{Homeo}(3)$ is decidable. However, we do not have efficient algorithms to solve this question. We do not even know how, in general, to estimate $c(M)$ within any fixed factor $K\ge 1$. The exact computation of $c(M)$ is only known for a finite number of examples (coming from various censuses) and some special families (Jaco, Rubinstein, Spreer, Tillmann). Estimating $c(M)$ to within a constant factor is known in some special families (Lackenby, Purcell, Jackson). In another other direction we have a question of Gromov:

The growth is at least exponential and at most exp-poly. We end this section with a question which feels, paradoxically, related to the above.

As a closely related problem, we should ask for a count of finite-volume cusped hyperbolic three-manifolds with complexity at most $n$. It may be possible to relate the counts, in the closed and cusped cases, by understanding how the complexity $c(M)$ changes under Dehn filling.

Suppose that $\mathrm{\Delta }$ is the four-simplex. We divide $\partial \mathrm{\Delta }$ combinatorially into a pair of triangulated three-balls, say $B$ and $B^{\prime }$. Let $k$ and $k^{\prime }$ be the number of tetrahedra in $B$ and $B^{\prime }$ respectively. Note that $k+k^{\prime }=5$.

Suppose that $𝒯$ is a triangulation of a three-manifold $M$. Suppose that a copy of $B$ appears as a subtriangulation of $𝒯$. Then we may produce a triangulation ${𝒯}^{\prime }$, again of $M$, by replacing the copy of $B$ in $𝒯$ by a copy of $B^{\prime }$. This move, from $𝒯$ to ${𝒯}^{\prime }$, is called a $k$-$k^{\prime }$ bistellar flip.

Suppose that $M$ is a compact connected three-manifold. We now define $\mathrm{GT}(M)$ to be the graph of triangulations of $M$: vertices are (isomorphism classes of) triangulations of $M$ and edges are bistellar flips. Note that $\mathrm{GT}(M)$ is connected (Pachner 1991). Navigation in the graph $\mathrm{GT}(M)$ is important both in theory and in practice.

If we restrict ourselves to geometric triangulations of hyperbolic manifolds $M$ (with a lower bound on injectivity radius) then $f_M$ is at worst cubic (Kalelkar, Phanse 2021). Supposing that such polynomials $f_M$ exist, we may ask the following.

One problem related to the above is as follows: fix a manifold $M$ and a number $k$ and then try to find a random triangulation $𝒯$ of $M$ with $k=c(𝒯)$. Another is as follows: fix a number $k$ and try to find a random manifold $M$ with $c(M)\le k$.

Suppose that $𝒞$ is a class of three-manifolds.

When $𝒞$ is the class of a single manifold $M$ then this reduces to $\text{Recog}(M)$. For example, recognising the three-sphere lies in the class $\mathrm{𝖭𝖯}$ (Schleimer 2011). More generally, recognising elliptic manifolds lies in the class $\mathrm{𝖭𝖯}$ (Lackenby, Schleimer 2022). The same holds for torus bundles over the circle (folklore) and Seifert fibred spaces with boundary (Jackson 2023).

This problem is decidable (Rubinstein 2004, Li 2006). One possible $\mathrm{𝖭𝖯}$-certificate might start by finding a fibre circle with length at most linear (in the complexity of the given triangulation).

This problem is decidable (Casson, Manning 2002). One possible $\mathrm{𝖭𝖯}$-certificate might start by finding a systole with at most linear length (in the complexity of the given triangulation).

This is a delicate question; the genus of the fibre may be exponentially large in the complexity of the given triangulation.

I thank Arnaud de Mesmay for his useful comments.

We investigate the problem of enclosing a subset of objects in the plane using a cycle of minimum total length. More specifically, given $n$ disjoint polygons in the plane, of total complexity $N$, and a number $k$, the problem is to find a minimum-perimeter weakly simple polygon containing exactly $k$ of the polygons. We also consider a variant of the problem where the $k$ polygons to be enclosed are specified as part of the input (see Figure 1). We are interested in the case where $k$ is small with respect to $n$, and aim for efficient algorithms in this fixed parameter setting.

We also consider a different, less geometric, setting where we are given as input a plane graph $G$ of total complexity $N$, a set of $n$ marked faces, an integer $k$, and we have to compute a shortest weakly simple closed walk in the graph that encloses exactly $k$ of the $n$ marked faces. As above, we also consider the variant where the $k$ faces to be enclosed are given as part of the input. The graph setting is more general than the polygon setting, via the following polynomial time reduction, which is based on the observation that the desired cycle walks on visibility edges: given a set of disjoint polygons, construct a plane graph by finding all visibility segments in the free space and adding vertices at their intersections to create a plane graph.

Other variants include the problem of enclosing at least $k$ objects (rather than exactly $k$), and – in the geometric setting – dealing with the presence of polygonal obstacles that may freely be included in, or excluded from, (but not cut by) the desired cycle.

These enclosure problems look very natural but seem rather unexplored, and are related to many well-studied problems, in particular Steiner tree and subset TSP. Our goal is to nail down the computational complexity of the problem and its many variations. We first survey related previous work and simple observations, and then present our results and other promising directions.

Both in the graph setting and in the geometric setting, we must allow the cycle or the boundary of the solution polygon to use the same edge more than once. Such a cycle, which may touch itself but must not cross, is called weakly simple. Figure 1 shows a symbolic drawing where the two copies of an edge are visually separated.

We have promising strategies to solve the following problem.

Note that if we only want to enclose $k$ polygons, without specifying the subset $Q$, we may enumerate each of the $n^{O(k)}$ subsets $Q$ of $P$ of size $k$ and apply the above result to each such subset $Q$ in turn.

We mimic the dynamic programming algorithm of Dreyfus and Wagner [7] that computes Steiner trees in graphs. We aim for an algorithm with running time $3^k\cdot N^{O(1)}$. The basic idea is to compute, for each subset $Q^{\prime }$ of $Q$ and each line segment $uv$, where $u$ and $v$ are input vertices, a shortest cycle $c(Q^{\prime },uv)$ having $uv$ on its boundary and such that a polygon has odd winding number with respect to the cycle if and only if the polygon lies in $Q^{\prime }$. No edge of $c(Q^{\prime },uv)$ may cross a polygon of $P$ except that $uv$ may cross polygons of $Q$. We expect to be able to compute the values of $c(Q^{\prime },uv)$ by increasing size of $Q^{\prime }$ by merging smaller solutions in the same spirit as the Dreyfus–Wagner approach. At the root of the recursion, we untangle the cycle to make it weakly simple without making it longer, and prove that it encloses precisely $Q$ by the condition on the winding numbers.

Possible improvements include removing the convexity assumption.

Lemma 1 implies that solving the problem exactly cannot be done in $2^{o(k)}\cdot N^{O(1)}$ time assuming ETH.

We can assume that , for otherwise it suffices to compute a weakly simple cycle homotopic to the outer face, which can be done in polynomial time. Let $X=P\setminus F$ be the set of faces that we want to exclude, and let $F=\{f_1,\mathrm{\dots },f_k\}$.

Let $(r_1,\mathrm{\dots },r_k)\in {\{0,\mathrm{\dots },N\}}^k$. Below, we describe a procedure that will return a feasible solution to the problem (if it returns anything at all). If, for every $i\in \{1,\mathrm{\dots },k\}$, $r_i$ equals the distance (in terms of the number of edges of a shortest path) from each face $f_i$ to $c_{\mathrm{OPT}}$, the procedure will return a solution, and it will be a $(k+2-2/k)$-approximation of the optimal solution. Our overall algorithm returns the shortest solution found by the procedure, over all choices of $(r_1,\mathrm{\dots },r_k)\in {\{0,\mathrm{\dots },N\}}^k$.

The procedure for a given $k$-tuple $(r_1,\mathrm{\dots },r_k)$ is the following.

1. 1.

   For each $i=1,\mathrm{\dots },k$, we remove all vertices at distance less than $r_i$ from $f_i$ (where the “distance” is the number of edges), enlarging $f_i$ to a larger face $f_i^{\prime }$. If some $f_i^{\prime }$ contains some face in $X$, we exit without returning anything. Let $G^{\prime }$ be the resulting graph.

2. 2.

   We describe a subroutine that computes a set $\mathrm{\Gamma }$ of cycles in $G^{\prime }$ satisfying, at each step of the subroutine, the following invariants:

   • $\mathrm{■}$

     the cycles in $\mathrm{\Gamma }$ are weakly simple and weakly pairwise disjoint;

   • $\mathrm{■}$

     they are pairwise non-nested;

   • $\mathrm{■}$

     no cycle in $\mathrm{\Gamma }$ encloses a face in $X$;

   • $\mathrm{■}$

     (*) for each cycle $\gamma$ in $\mathrm{\Gamma }$, there is a face $f\in F$ such that $\gamma$ is, in ${ℝ}^2\setminus (X\cup f^{\prime })$, a shortest cycle homotopic to the boundary of $f^{\prime }$ (in $G^{\prime }$).

   At the end of the subroutine, each face of $F$ is enclosed by a (unique) cycle in $\mathrm{\Gamma }$.

   Here is the subroutine. Initially, $\mathrm{\Gamma }$ is empty. While some face $f$ of $F$ is enclosed by no cycle in $\mathrm{\Gamma }$, we do the following:

   1. (a)

      Let $\gamma$ be the shortest cycle in $G^{\prime }$ among those that are weakly disjoint from $\mathrm{\Gamma }$ and homotopic, in ${ℝ}^2\setminus \{X\cup f^{\prime }\}$, to the boundary of $f^{\prime }$. We can compute $\gamma$ in near-linear time as follows: Remove the interior of each cycle in $\mathrm{\Gamma }$, and then compute a shortest cycle homotopic, in ${ℝ}^2\setminus \{X\cup f^{\prime }\}$, to the boundary of $f^{\prime }$, using, e.g., [3, Lemma 4.1]; $\gamma$ will automatically be weakly simple.

   2. (b)

      Add $\gamma$ to $\mathrm{\Gamma }$, and then remove from $\mathrm{\Gamma }$ all cycles enclosed by $\gamma$, if any.

   The process clearly terminates after at most $k$ steps. The invariants are clearly satisfied, except the last one (*), which we can prove separately. (It suffices to prove that some shortest cycle homotopic, in ${ℝ}^2\setminus \{X\cup f^{\prime }\}$, to the boundary of $f^{\prime }$ is weakly simple and weakly disjoint from $\mathrm{\Gamma }$, and we omit the proof here.)

3. 3.

   We compute a minimum spanning tree $\widehat{T}$ in an auxiliary graph $\widehat{G}$, which is a complete graph with a node for every cycle in $\mathrm{\Gamma }$. The edge weights are the shortest distances between the corresponding cycles in $G^{\prime }$. Every edge of $\widehat{T}$ corresponds to a path in $G^{\prime }$. When we overlay these paths they form a subgraph $\overline{T}$ that connects the cycles in $\mathrm{\Gamma }$. We remove multiple edges from $\overline{T}$ and (conceivably) edges that create cycles in $\overline{T}$, until we end up with a forest $T$ that still connects the cycles in $\mathrm{\Gamma }$. ($T$ is a Steiner tree in the graph where each cycle in $\mathrm{\Gamma }$ and its interior is contracted into a single vertex.)

4. 4.

   We combine $T$ and the cycles in $\mathrm{\Gamma }$ to obtain a weakly simple cycle of length $2w(T)+w(\mathrm{\Gamma })$ enclosing the faces of $F$ but no face of $X$; see Figure 2.

The running time of the overall algorithm is clearly $N^{O(k)}$.

It remains to bound the length of the output. Let $c_{\mathrm{OPT}}$ be a shortest weakly simple cycle enclosing $F$ but no face of $X$. We consider the cycle $c$ obtained in the previous procedure in the case where $r_i$ is the graph distance from $c_{\mathrm{OPT}}$ to $f_i$. It suffices to prove that $w(c)\le (k+2-\frac{2}{k})w(c_{\mathrm{OPT}})$. We have $w(c)=2w(T)+w(\mathrm{\Gamma })$, where $T$ and $\mathrm{\Gamma }$ are obtained in the iteration computing $c$. Moreover, by the choice of the $r_i$’s:

• $\mathrm{■}$

  Each of the at most $k$ cycles $\gamma$ in $\mathrm{\Gamma }$ is no longer than $c_{\mathrm{OPT}}$. Indeed, by Property (*), $\gamma$ is a shortest cycle homotopic to the boundary of $f^{\prime }$ in ${ℝ}^2\setminus (X\cup f^{\prime })$, for some $f\in F$, and $c_{\mathrm{OPT}}$ is homotopic to the boundary of $f^{\prime }$ in ${ℝ}^2\setminus (X\cup f^{\prime })$, for each $f\in F$.

• $\mathrm{■}$

  $w(T)\le w(c_{\mathrm{OPT}})\frac{k-1}{k}$, because $c_{\mathrm{OPT}}$ is connected and intersects the boundary of each cycle in $\mathrm{\Gamma }$ (perhaps unless $\mathrm{\Gamma }$ is a single cycle, in which case the claim is still true). Let $p_1,\mathrm{\dots },p_{k^{\prime }}$ be intersection points between $c_{\mathrm{OPT}}$ and the $k^{\prime }\le k$ cycles of $\mathrm{\Gamma }$, in the order in which they are visited by $c_{\mathrm{OPT}}$. Then the sections of $c_{\mathrm{OPT}}$ from $p_1$ to $p_2$, from $p_2$ to $p_3$, etc, from $p_{k^{\prime }-1}$ to $p_{k^{\prime }}$, whose total length is bounded by $w(c_{\mathrm{OPT}})$, yield an upper bound on the weight of the minimum spanning tree $\widehat{T}$ in Step 3, and hence $w(T)\le w(c_{\mathrm{OPT}})$. By cyclically shifting the sequence $p_1,\mathrm{\dots },p_{k^{\prime }}$ such that the omitted section from $p_{k^{\prime }}$ for $p_1$ is the longest among the $k^{\prime }$ segments, the bound is improved by the factor $\frac{k^{\prime }-1}{k^{\prime }}\le \frac{k-1}{k}$.

∎

We are given a smooth closed curve in the plane, described by a function $\gamma :S^1\to {ℝ}^2$, and two points $a$ and $b$ on the curve. Here $a$ is the attractor (think of a magnet) and $b$ is a ball (think of an iron or nickel ball). Then $b$ always moves closer to $a$ if possible while staying on the curve. We can directly control the position $a$, but we have no direct control over $b$. We assume that $b$ moves infinitely faster than $a$. Our goal is to move $a$ along the curve in such a way that $a$ meets $b$ (see Figure 3). Note that a bit of care is required to properly define this problem and make sure $\gamma$ is generic enough for the conversation to hold. For more details and a careful description of the setting, see [1, 3.1].

It is known that for every simple curve $\gamma$ (that is, without self-intersections), there always exists strategy to catch the ball from every initial configuration [1].

It is also known that there exist curves for which this is not possible; the simplest such curve is the “doubled circle”, and in fact any curve that is “doubled” or “multipled” is an example of such a curve, since $a$ and $b$ will always stay close to each other on different “copies” of the curve. Refer to Figure 4 for some examples; for proper definitions and proofs see [1].

A natural question is then to see whether one can characterise those curves for which there does exist a strategy to catch the ball from every initial configuration. Perhaps the first and simplest invariant of a curve is the rotation number (also called the index or Whitney index). This is defined as the number of revolutions a tangent vector completes as it traverses the curve once. It is related to the number of left-to-right and the number of right-to-left crossings of the curve. [3]

A question posed in [1] is:

Experimental evidence suggests the answer should be yes. You can play around with an implementation here to try for yourself: https://github.com/viglietta/Chasing-Puppies

Persistent homology [4] studies the evolution of the homology of the level-sets

of a continuous function $f:X\to ℝ$ on a topological space $X$. A most studied situation is when the space $X$ is the Euclidean space ${ℝ}^d$, and the function $f$ is the Euclidean distance function to some compact subset of ${ℝ}^d$. Available implementations, such as in the Gudhi library [5], essentially work with finite point set approximations of compacts.

In our framework, the ambient space is the 3-dimensional Euclidean space ${ℝ}^3$, the compact subset is the collection of closed polygonal curves $L$ forming the link, and an $r$-thickening of $L$ is the level set $f^{-1}((-\mathrm{\infty };r])$ of the function $f$ assigning to any point $x\in {ℝ}^3$ the distance from $x$ to $L$.

We propose a heuristic solution to the link thickening problem with good practical performance, based on persistent homology. For implementation reasons, it is easier to work with neighborhoods of point clouds, instead of polygonal curves. We start by subsampling the polygonal curves of $L$ with a collection of regularly spaced points $P\subset L$. Let $ϵ$ be the density of $P$ in $L$, i.e., the maximal distance between $L$ and $P$:

Heuristically, we assume by subsampling sufficiently.

Call ${\mathrm{d}}_P:{ℝ}^3\to ℝ$ the distance function to the point cloud. Let $n$ be the cardinality of $P$, and $k$ the number of connected components of the link $L$.

In practice, the topology of the level sets ${\mathrm{d}}_P^{-1}\left((-\mathrm{\infty };r]\right)$, consisting of the union of balls of radius $r$ centered at the points in $P$, follows several phases for $r>0$:

Phase 1

for , the level set ${\mathrm{d}}_P^{-1}\left((-\mathrm{\infty };r]\right)$ is a collection of strictly more than $k$ connected components,

Phase 2

for , the level set ${\mathrm{d}}_P^{-1}\left((-\mathrm{\infty };r]\right)$ has the homotopy type of $L$,

Phase 3

for , the level set ${\mathrm{d}}_P^{-1}\left((-\mathrm{\infty };r]\right)$ does not have the homotopy type of $L$.

Intuitively, the phase consists of $n$ disjoint radius $r$-balls centered at the points in $P$ when $r$ is close to $0$, that eventually merge into a regular neighborhood of the link $L$, once .

For , and under valid density assumptions [1], the level set ${\mathrm{d}}_P^{-1}\left((-\mathrm{\infty };r]\right)$, or equivalently the union of balls of radius $r$ centered at the points of $P$, is guaranteed to have the same homotopy type as the link $L$, i.e.,, a collection of $k$ circles.

When passing the critical value $r=r^{\ast }$, the topology of ${\mathrm{d}}_P^{-1}\left((-\mathrm{\infty };r]\right)$ changes by definition, which happens in three possible ways: generically,

Case 1

either one component $K$ of the link $L$ fills up, in which case a solid torus neighborhood of $K$ turns into a 3-ball,

Case 2

or a component $K$ of the link $L$ self intersects, in which case a solid torus neighborhood of $K$ turns into a genus 2 handlebody,

Case 3

or two distinct components $K_1,K_2$ of the link $L$ connect to form a genus 2 handlebody.

All three cases are captured by the homology of ${\mathrm{d}}_P^{-1}\left((-\mathrm{\infty };r]\right)$. Indeed, in case 1, the dimension of the first homology group $H_1({\mathrm{d}}_P^{-1}\left((-\mathrm{\infty };r]\right),{\mathbb{Z}}_2)$ is reduced by $1$. In case 2, the dimension of $H_1({\mathrm{d}}_P^{-1}\left((-\mathrm{\infty };r]\right),{\mathbb{Z}}_2)$ increases by $1$. Finally, in case 3, the number of connected components, which is equal to the dimension of the homology group $H_0({\mathrm{d}}_P^{-1}\left((-\mathrm{\infty };r]\right),{\mathbb{Z}}_2)$, decreases by $1$.

All cases are readily available from the persistent diagrams of the level sets of the function ${\mathrm{d}}_P^{-1}$.

The Cech complex based on $P$ and of threshold $r$ is a simplicial complex which has the same homotopy type as the level set ${\mathrm{d}}_P^{-1}\left((-\mathrm{\infty };r]\right)$. However, it is challenging and relatively slow to implement its construction, in comparison to the Rips complex [4]. Rips complexes can be interpreted as an approximation of the Cech complex, and are generally preferred in software implementation. When their construction is extremely fast [2], they result into noisier persistence diagrams. However, in our context where $P$ is a noiseless subsample of a link in ${ℝ}^3$, we do not observe experimentally significant differences in the persistence diagrams of the two filtered complexes.

We interface the Gudhi library with Regina to implement the algorithm above. For efficiency reasons, we stop the computation when the change of homology at $r=r^{\ast }$ is detected. First experiments show a close to real time performance on simple knots and links. See Figure 10 for an example of rendering.

A connected normal surface is vertex linking if it contains only triangles. In a closed 3-manifold, a vertex linking surface will be sphere that is the boundary of a regular neighborhood of some vertex of the triangulation. Each vertex of a triangulation has a vertex linking sphere surrounding it, are there any other normal spheres? A 3-manifold triangulation is 0-efficient if there are none, i.e., all of its normal spheres are vertex linking. Almost all 3-manifolds have a 0-efficient triangulation and working with one yields significant computational advantages [5, 2].

The working group was formed to consider the computational complexity of the following problem:

Alternatively, we can consider the complementary problem:

The work of Hass, Lagarias, and Pippenger [4] shows that if there is a non-vertex linking normal sphere, then there is one with an (exponentially) bounded number of triangles and quadrilaterals. This determines a coordinate vector with linear bit-length which is sufficient to certify that the underlying normal surface is a non-vertex linking sphere. It follows that Problem 2 is in NP (and Problem 1 is in co-NP).

The working group endeavored to show that Problem 2 is also NP-hard, primarily by demonstrating a reduction from a problem such as 3-SAT. One possible model is the work of Agol, Hass and Thurston [1], who used a reduction from 3-SAT to show that the problem 3-Manifold Knot Genus is NP-hard. Unfortunately, it seems quite challenging to adapt their approach to Problem 2. In particular, their reduction yields surfaces with large genus, whereas Problem 2 would require a reduction that always produced a sphere.

The group also considered various analogues and/or variations on Problems 1 and 2, see the sections below. Towards the end of the group’s meetings, a proposal was made to weaken Problem 2 to allow surfaces of higher genus:

A subcomplex linking surface is a normal surface that links a subcomplex of the triangulation. Vertex linking spheres are the simplest case, and always exist, but it is also possible that a normal surface links an edge or even a larger subcomplex of the triangulation.

It seems possible that Problem 3 is NP-hard. This appears easier to approach than showing that Problem 2 is NP-hard.

The working group also considered the computational complexity of deciding whether a given knot is composite. In particular, we believe that the following problem is in NP:

Typically a knot is specified by providing a knot diagram, a projection of the knot into the plane, with its over and under crossings indicated. A few observations are helpful:

1. 1.

   A composite knot is characterized by the existence of an decomposing annulus, a meridional essential annulus that is properly embedded in the knot exterior, $X=S^3-\eta (K)$, where $\eta (K)$ is an open tubular neighborhood of $K$. The knot exterior is a compact manifold with a single torus boundary component. Cutting the exterior $X$ along the decomposing annulus, cuts the knot exterior into the exteriors of the knots $K_1$ and $K_2$.

2. 2.

   Given a diagram of a knot drawn in the plane with $c$ crossings, it is straightforward to produce a triangulation of the knot exterior with at most $O(c)$ tetrahedra [4].

Using these observations we can recognize a composite knot by decomposing along this annulus. In particular, we need to

1. 1.

   Produce the decomposing annulus $A$, and

2. 2.

   Show that when $X$ is cut along $A$, each of the resulting components is a non-trivial knot exterior.

We may assume that the knot exterior $X$ is given by a 0-efficient triangulation. Then, some decomposing annulus $A$ is realized as a fundamental normal surface. In particular, this means that its coordinates (number of triangles and quadrilaterals) are bounded exponentially and the bit size of the coordinate vector is linear in the number tetrahedra. The coordinate vector of this annulus will serve as the NP certificate. Indeed, using the coordinate vector, we can verify that it represents an incompressible annulus.

It remains to show that when $X$ is cut along $A$, the two knot exteriors produced are non-trivial (equivalently, that the annulus $A$ is not peripheral in $X$). For this we can use Lackenby’s result that the unknotting problem is in co-NP [8]. Unfortunately, naively cutting $X$ along $A$ will not be sufficient as the resulting triangulation is only exponentially bounded. Three alternatives were proposed to mitigate this complication:

1. 1.

   Cut in a smarter way so that the resulting triangulation (or handle structure) has polynomial (linear?) complexity in terms of the original.

2. 2.

   Crush $X$ along the annulus $A$ instead of cutting along it [5, 2]. This is equivalent to Dehn filling the meridian (producing $S^3$) and then crushing along a capped off sphere. This reduces the number of tetrahedra, but we would need to prove that knowledge of the summands can be tracked through the crushing procedure.

3. 3.

   Work with a spun normal annulus in an ideal triangulation. We would need to show that a peripheral annulus would not occur as a spun normal annulus.

Each of these approaches holds promise and would require working out some significant details. Regardless, this result appears to be the most attainable considered by the group.

The working group also discussed the complexity of ribbon knot recognition with the aim of showing that this problem is in NP for small knots:

A small knot is a knot with no closed essential surfaces in its exterior. Every knot $K\subset S^3$ bounds an immersed disk. A knot $K$ is a ribbon knot, if it bounds a ribbon disk an immersed disk $D$ with only ribbon singularities. A ribbon singularity is an arc of self intersection whose pre-image in the disk consist of two arcs, one arc in the interior of the disk (a slit) and one arc with both endpoints in the boundary of the disk (the ribbon passing through the slit).

Given a ribbon knot, choose a ribbon disk that minimizes the number of ribbon singularities. Each of the, say $n$, ribbon singularities can be desingularized, in two distinct ways, by a cut and paste of the two sheets that meet the singularity. Resolving all $n$ singularities produces a Seifert surface for the knot with Euler characteristic $1-2n$.

While there are clear cases where bad choices produce a compressible surface, an affirmative answer yields an approach to ribbon knot recognition.

Suppose that there is a desingularization producing an incompressible surface $F$. When the knot $K$ is small, $F$ will be realized by a fundamental normal surface. (If $F$ is a normal sum, then one of the summands is a closed essential surface contradicting that $K$ is small [7, 6]).

The goal would then be to exhibit an NP certificate consisting of the fundamental normal surface $F$ along with a collection of $n$ disks in its complement that demonstrate how to resingularize the surface to produce a ribbon disk for $K$.

Currently, resolving Question 6 is the main obstacle to this approach. A first step could be gathering evidence using Burton’s Regina [3].

Flip graphs – graphs whose vertices are the triangulations of a geometric or topological space and whose edges correspond to a local operation between them called a flip – appear naturally in computational geometry [15, 20, 24] and in low-dimensional topology [2, 9, 17]. When the triangulated space is a convex polygon, that graph is also relevant to algebraic combinatorics since in that case, it is precisely the edge graph of the associahedron [14], a polytope that has been generalized in a number of ways [5, 10, 11, 21].

The geometry of flip graphs has attracted considerable attention because it is intimately connected to the complexity of balancing binary trees [27], provides a dissimilarity measure between these trees [7], serves as a combinatorial model for the mapping class group of a surface [9, 17], or can be used as a tool to optimize triangulations [1, 3, 4]. The diameter of the associahedron is known exactly [23], but the complexity of computing the distance between two of its vertices is still an open problem [15, 20].

This note has two parts. In Section 4.7.2, we discuss two natural heuristics to find short paths between triangulations of the convex $n$-gon and show how they are linked. The heuristics use what is called shadow vertex paths and crossing-monotone flip sequences. We then present a family of pairs of triangulations for which one of these heuristics performs worst possible, up to a constant factor, and discuss implications for the other heuristics. In Section 4.7.3 we prove upper and lower bounds on flip distances in the modular flip graph of triangulations of the annulus with $n_1$ and $n_2$ marked points on its boundary components, $n=n_1+n_2$. More specifically, we prove that the diameter of this flip graph must lie between $\frac{9}{4}n$ and $\frac{10}{4}n$, see Lemmas 9 and 10.

In this section, we consider the flip graph $ℱ(P)$ of a Euclidean convex $n$-gon $P$. A triangulation of $P$ is a set of pairwise non-crossing arcs between the vertices of $P$ that decompose $P$ into triangles. In this context, an arc is just a straight line segment. The vertices of $ℱ(P)$ are the triangulations of $P$ and its edges link and pair of triangulations that differ by exactly one arc. It is well-known that $ℱ(P)$ is the edge graph of the $(n-3)$-dimensional associahedron [14].

We consider two natural heuristics for computing short flip sequences between two given triangulations ${𝒯}_1$ and ${𝒯}_2$ of a convex $n$-gon:

1. 1.

   Shadow vertex paths are obtained by projecting the associahedron onto a plane. The two directions defining the projection (the shadow) are chosen such that vertices corresponding to ${𝒯}_1$ and ${𝒯}_2$ are both extremal. Then, the projection is used to describe a sequence of flips turning ${𝒯}_1$ into ${𝒯}_2$. The resulting flip path depends on the chosen realization of the associahedron and on the choice of directions for ${𝒯}_1$ and ${𝒯}_2$ in their respective normal cones. A natural choice of realization of the associahedron is the realization as a secondary polytope for a regular $n$-gon.

2. 2.

   Superimpose ${𝒯}_1$ and ${𝒯}_2$. A crossing-monotone path is a sequence of flips, strictly reducing the number of crossing pairs of arcs between ${𝒯}_2$ and the intermediate triangulations obtained from ${𝒯}_1$ at each step.

We show how these two heuristics are linked, obtain negative results for the first heuristic, and discuss the implications on the second. More precisely, we present pairs of triangulations, where the path constructed by the first heuristic is of length $O(n^2)$. This path realizes the worst case asymptotics and is much longer than the actual shortest path of length $O(n)$.

Consider an orientable surface $\mathrm{\Sigma }$ equipped with a finite set of points such that each boundary component of $\mathrm{\Sigma }$ contains at least one of these points. By a triangulation of $\mathrm{\Sigma }$, we mean an inclusion-wise maximal set of pairwise non-crossing arcs on $\mathrm{\Sigma }$ between two of these prescribed points. Note that the arcs are considered up to isotopy, so in particular, when we say that two arcs are non-crossing, this means that two representatives in the corresponding isotopy classes are non-crossing. The flip graph $ℱ(\mathrm{\Sigma })$ of $\mathrm{\Sigma }$ is the graph whose vertices are the triangulations of $\mathrm{\Sigma }$ and whose edges correspond to flipping arcs.

The modular flip graph $ℳℱ(\mathrm{\Sigma })$ of $\mathrm{\Sigma }$ is obtained by quotienting $ℱ(\mathrm{\Sigma })$ by the homeomorphisms of $\mathrm{\Sigma }$ that fix the vertices of the triangulations pointwise [17]. It is known that when $\mathrm{\Sigma }$ is an annulus with $n$ points on one boundary and a single point on the other, the diameter of the modular flip graph of $\mathrm{\Sigma }$ is exactly $\lfloor 5n/2\rfloor -2$ [17, Theorem 1.4]. In this section, we consider the slightly more general case when $\mathrm{\Sigma }$ is an annulus with $n_1$ points on one boundary and $n_2$ on the other, with $n=n_1+n_2$. We aim at bounding the worst-case diameter of the modular flip graph of $\mathrm{\Sigma }$ as a function of $n$.