Computational Geometry

The setting is a 3-manifold triangulation. A normal surface is a properly embedded surface that meets each tetrahedron in some collection of triangles and/or quadrilaterals (e.g., no tubes, no bubbles, no octagons, etc.).

The main bottleneck for unknot recognition, 3-sphere recognition, prime decomposition and some other core 3-manifold algorithms is this: find a non-trivial connected normal surface with positive Euler characteristic, or determine that no such surface exists. Here non-trivial means that the surface is not just a collection of triangles that build a sphere around a vertex (in other words, there is at least one quadrilateral).

Currently the best known running time is $O(3^n\cdot \mathrm{poly}(n))$, where $n$ is the number of tetrahedra. However, it seems plausible that this could be FPT in the treewidth of the dual graph of the triangulation. If so, this would give immediate FPT results for several important topological algorithms (e.g., those listed earlier).

Some further notes: normal surfaces are described by vectors in ${ℝ}^{7n}$ (each entry counts the number of triangles or quadrilaterals in some position in some tetrahedron). These vectors must satisfy some linear equations, linear inequalities, and combinatorial constraints. The inequalities and combinatorial constraints are local to each tetrahedron, and the equations come from gluings between adjacent tetrahedra. In this sense, the structure of the equations mirrors the structure of the dual graph, which is one reason such an FPT result might be plausible.

It is also an open problem to prove that this same problem is NP-hard.

Let $T$ be an arbitrary planar straight-line triangulation, with a triangular outer face, such that the origin $(0,0)$ lies in the interior of some bounded face, and no two vertices lie on the same line through the origin. An eversion of $T$ is another planar straight-line triangulation satisfying three conditions:

• $\mathrm{■}$

  $T$ and $T^{\prime }$ are embeddings of the same maximal planar graph $G$.

• $\mathrm{■}$

  Every vertex of $G$ lies on the same ray from the origin in both $T$ and $T^{\prime }$.

• $\mathrm{■}$

  For every ray $r$ from the origin, the sequence of edges of $T$ that $r$ intersects is the reversal of the sequence of edges of $T^{\prime }$ that $r$ intersects. Equivalently, every face of $T$, except the outer face and the face containing the origin, has the opposite orientation of the corresponding face of $T^{\prime }$. (The outer face of $T$ must be the face containing the origin in $T^{\prime }$, and vice versa.)

A structure that might cause complications are “rotors” or “lens-shutters”. Essentially, this is a sequence of $e_0,\mathrm{\dots },e_k$ of disjoint line segments that cyclically overlap, such that for each $i$ along the ray through of one endpoint of $e_i$, the intersection with $e_{i+1modk}$ lies closer to the origin than the endpoint. I’ll call this endpoint the “far endpoint” $f_i$ of $e_i$. Equivalently, every edge of a rotor also has a “near endpoint” $c_i$. Less formally, all near endpoints are visible from the origin, but no far endpoints.

Rotors are the simplest sets of segments that do not have a radial shelling order. A radial shelling order indexes the segments $s_1,s_2,\mathrm{\dots },s_n$, so that if any line segment from the origin to any segment $s_i$ crosses another segment $s_j$, then . Arguments of of Awartani and Henderson [2, 3] imply that any set of segments that is radially shellable has an eversion.

An argument of Pallazi and Snoeyink [4] implies that if any ray from the origin misses all the segments, then the segments are radially shellable. Thus, rotors must surround the origin.

Further, we asked whether it might be that a rotor can be drawn with straight edges but needs a very specific shape of the polygon $F=f_0,\mathrm{\dots },f_k$ formed by the far endpoints. We think that we can prove the following: If there is a realization in which $F$ is a star-shaped polygon, then there is also a realization where the vertices of $F$ lie on a circle, or any other convex polygon. Likewise, there should be one for any star-shaped polygon $F$ (with the vertices obeying the given angle condition).

It is still unclear whether a proof that every rotor can be everted would imply that any planar straight-line graph, or even every set of disjoint segments, can be everted.

A geodesic on the sphere is any arc of a great circle. A geodesic is long if it contains two antipodal points and short otherwise; every short geodesic is the unique shortest path between its endpoints. (Classically, the word “geodesic” refers only to shortest paths on the sphere; here I’m using the more general definition from Riemannian geometry.)

A geodesic embedding of a graph $G$ on the sphere maps the vertices of $G$ to distinct points and the edges of $G$ to interior-disjoint geodesics. A geodesic embedding is short if each of its edges is short, and long otherwise.

Computing persistent homology usually takes time linear in the number of cells of the filtered complex involved. To speed things up, one then needs a small complex. The first (geometric) approach is to define a small complex to begin with. The second (combinatorial) approach, the one I am interested in today, is to simplify a filtration before computing its persistent homology. This only makes sense if we can simplify the complex without actually listing its cells explicitly (same cost as computing PH). A common case is flag filtrations (like Vietoris-Rips), which can be represented by a graph with a filtration value for each vertex and edge, and where higher dimensional cells are implicitly defined as the cliques of the graph. The goal of the simplification is then to replace the graph with a smaller graph before listing its simplices to compute PH (so there are fewer simplices to list).

Glisse and Pritam [1] provide an approach for simplifying the graph while exactly preserving its PH. However, in many cases, we would be happy with an approximation.

The following approaches and questions arose during the seminar.

• $\mathrm{■}$

  Forcibly reintroduce some geometry, embedding in dim log n.

• $\mathrm{■}$

  Could rounding to a grid be more efficient than what the paper does, sometimes, because it gives some edges the same value and thus helps jump over them? Needs experiments; but initial experiments showed this did not provide an improvement.

• $\mathrm{■}$

  Simplification with Morse matching (not at the graph level, just a first step to understand what is possible?)

It was also suggested to maybe we use function approximation coresets to get some sort of approximation relevant for persistence (diagram) approximation using function approximation coresets. For instance in the line of work by Langberg and Schulmann [2] or and more recently (and perhaps more generally) by Alishahi and Phillips [3]. Constructions like Growing Neural Gas [4] could be viewed as an approximation of what we want, and could be further generalized. Funke and Ramos work on smooth-surface reconstruction [5] might also be helpful.

The treewidth $\mathrm{tw}(M)$ of a compact 3-manifold $M$ is defined as the smallest treewidth the dual graph $\mathrm{\Gamma }(T)$ of any generalized triangulation $T$ of $M$ may have. In other words

The study of $\mathrm{tw}(M)$ is motivated by existing fixed-parameter tractable (FPT) algorithms to efficiently compute various 3-manifold invariants from triangulations with dual graph of bounded treewidth [1, 2, 3, 4, 5] – several of which are known to be NP-hard in general. The treewidth has been related to various other properties of 3-manifolds, such as Heegaard genus [7, 9], hyperbolic volume [10] (cf. [6]), or JSJ decompositions [8], but several fundamental questions remain to be answered.

During the seminar, we focused primarily on Questions 2 and 3.

Given a geometric graph $G=(V,E)$ where the vertices are points in the plane and the edge weights is the Euclidean distance between its endpoints, the main goal is to construct a $(1+\epsilon )$-approximate distance oracle ($O(1))$ query time) using linear space and $O(m+n\log n)$ preprocessing.

Of course this is not possible for arbitrary geometric graphs, instead we want to investigate restricted graph classes. In particular, we want to investigate graph classes that include road networks (think about queries in Google maps). Such a graph class should allow for edge intersections and include naturally occurring graphs such as grid graphs or “cul-de-sac” graphs. There are a number of “realistic” graph classes, e.g. planar, low-dilaton, $c$-packed, small highway dimension, small skeleton dimension, and small doubling dimensions that allow for approximate distance oracles, but these graph classes do not include road networks.

There are a few graph classes that include road networks, e.g. disk neighbourhood, crossing degeneracy, and bounded growth graphs but they do not have efficient algorithmic tool sets. Our favourite natural graph class that includes road networks is $\lambda$-low density graphs or the more general class of $\tau$-lanky graphs. A geometric graph is $\lambda$-low density if for every $p$ and $r$ the ball $B(p,r)$ with centre at $p$ and radius $r$ intersects at most $\lambda$ edges of $E$ of length at least $r$.

In a recent paper [1] we showed that $O(1)$-low-density graphs have a $(1+\epsilon )$-approximate distance oracle using $O(n\log n)$ space and $O(n^{3/2}polylogn)$ preprocessing. The key insight used to obtain this result is a Well-Separated Pair Decomposition (WSPD) of $V$ in the graph metric of $O(n\log n)$ size (which gives the space bound). There are two natural techniques that could be used to improve this result:

1. 1.

   Improve the size of the WSPDs for low density graphs. No non-trivial lower bound is known. Can we close the gap between $\mathrm{\Omega }(n)$ and $O(n\log n)$? Unit disk graphs (UDG) have the same bounds. Even subgraphs of a grid graph would be interesting (or even a tree in a grid graph). In dimensions greater than 2 the lower bound for the WSPD for UDG is $\mathrm{\Omega }(n^{2-2/d})$.

2. 2.

   Find a tree cover $T_1,\mathrm{\dots },T_k$ of $G$ of constant size and $(1+\epsilon )$ dilation. A tree cover is a set of trees s.t. for every pair of points $p$ and $q$ (a) there exists a tree $T_i$ with $d_{T_i}(p,q)\le (1+\epsilon )\cdot d_G(p,q)$ and (b) for every tree $T_i$ $d_{T_i}(p,q)\ge d_G(p,q)$. If such a tree cover exists we would probably get a $(1+\epsilon )$-approximate distance oracle of linear space.

Any results for 1 or 2 would give improved results.

Given a graph $G=(V,E)$ with a weight function $w:E\mapsto {ℝ}_{+}$, the problem is to compute a consistent system $𝒫$ of shortest paths w.r.t. to $w$, so that for every $u,v\in V$ there is a shortest path from $u$ to $v$ in $𝒫$ and for every paths $p,q\in 𝒫$ their intersection is connected (possibly empty), i.e. is a commmon subpath.

If shortest paths are unique for the weight function, then the set of shortest paths is consistent. There are various perturbation schemes that ensure uniqueness of shortest paths, either non-deterministic or deterministic but with an extra overhead in complexity (see discussion below). The goal here is to produce a consistent system of shortest paths in a deterministic way with no overhead cost compared to the traditional all-pair-shortest-paths algorithms. The hope is to compute a consistent system in a more efficient way, without enforcing uniqueness of shortest paths…

Computing a consistent system of shortest paths appears to be equivalent to compute a consistent system of rooted shortest path trees. Here, consistent means that for every $u,v\in V$, the (shortest) path from $u$ to $v$ in the tree $T_v$ rooted at $v$ is the reverse of the path from $v$ to $u$ in the tree $T_u$ rooted at $u$, i.e. $T_v(u)={(T_u(v))}^{-1}$

This last characterization is itself equivalent to the following: for every $u,v\in V$

1. 1.

   $T_v(u)$ and $T_u(v)$ have the same number of edges, and

2. 2.

   denoting by ${\pi }_u$ the parent pointer in $T_u$, either ${\pi }_v(u)=v$ or ${\pi }_v(u)={\pi }_{{\pi }_u(v)}(u)$.

The first condition is easily enforced by adding a constant perturbation to the edge weights. The second is “local” in the sense that it only involves pointer comparisons (as opposed to compare the paths $T_v(u)$ and $T_u(v)$).

A simple randomized perturbation of the edge weights provides uniqueness of shortest paths with high probability. The perturbations are obtained by drawing independently and uniformly at random an integer in $[1,n^4]$ for every of the $n$ edges. See [1, Sec 6.1] for a full description of this non-deterministic perturbation scheme based on the Isolating Lemma of Mulmeley, Vazirani and Vazirani [2].

There are two known deterministic approaches to compute weight perturbations to guarantee uniqueness of shortest paths for graphs embedded on surfaces.

• $\mathrm{■}$

  One uses lexicographic perturbation, incurring a $O(\log n)$ overhead [1]. This perturbation scheme assigns a unique index to each edge in the graph, and then breaks ties between shortest paths by comparing the lexicographically smallest index where the two paths differ. The scheme uses a dynamic-forest data structure to maintain a shortest-path tree during its construction via Dijkstra’s algorithm. In addition to uniqueness, this scheme guarantees that shortest paths are symmetric: The reversal of any shortest path is also a shortest path.

• $\mathrm{■}$

  The other scheme uses homology and incurs a $O(g)$-factor overhead [3]. This “holiest” perturbation scheme uses a vector of $2g+1$ perturbation terms for each edge, $2g$ of which are homology signatures, and the last of which stores the number of vertices in a fixed dual spanning tree on one side of the edge. Path lengths are vectors of length $2g+2$, which are added as vectors and compared lexicographically. This is a generalization of the leftmost-shortest path tie-breaking rule for planar graphs, originally proposed by Ford and Fulkerson. Like the leftmost shortest paths in planar graphs, holiest shortest paths are not necessarily symmetric. Consider two opposite corner vertices in a square unweighted grid graph.

It should be emphasized that the main problem here is not making individual edge weights distinct, but making certain sums of edge weights distinct.

Raimund Seidel points out that the Floyd-Warshall all-pairs shortest path algorithm computes a consistent set of shortest paths. Recall that the $i$th iteration of Floyd-Warshall computes the shortest path from each vertex $u$ to each vertex $v$ whose intermediate vertices have index at most $i$. It follows that FW computes shortest paths that lexicographically minimize the sorted vector of vertex indices.

Unfortunately, Floyd-Warshall runs in $O(n^3)$ time, which is more than we want to spend for most surface-graph algorithms.

It appears that Wullf-Nilsen already described a similar perturbation scheme for arbitrary graphs that allows Dijkstra to compute paths that minimize length, then the number of edges, and finally the sorted vector of vertex indices, all in $O(n\log n)$ time [4] for a single shortest path tree. By repeating Dijkstra from every vertex we thus obtain a consistent system of shortest paths in $O(n^2\log n)$ time. Note that Wullf-Nilsen uses $O(\log n)$ extra pointers per vertex, so that running a single (modified) Dijkstra actually uses $O(n\log n)$ space instead of the usual linear space implementation. In fact, Hartvigsen and Mardon [6] formerly described an implementation that runs all the Dijsktra’s in parallel in $O(n^2\log n)$ time without using extra pointers.

See also Borradaile, Sankowski, and Wulff-Nilson [5, Sec. 7] for an implementation using top trees.

This is the basis for the $O(\log n)$-factor lexicographic perturbation scheme described above; the $O(\log n)$ overhead does not apply to Dijkstra’s algorithm, but rather to the pivots inside our multiple-source shortest paths algorithm. Similarly, Borradaile, Sankowski, and Wulff-Nilson show that more modern shortest-path algorithms based on dense-distance graphs incur a $O({\log }^{2}n)$ overhead.

In a graph tiling problem, we are given as input a set of square tiles with pieces of graph drawn (embedded) on them, and the output is an arrangement of those tiles into a larger area, like in Figure 2.

Now, we are interested in output arrangements that satisfy certain properties.

• $\mathrm{■}$

  Tiles should “match up” on the sides.

• $\mathrm{■}$

  We may want that the resulting graph is connected.

• $\mathrm{■}$

  We may want to minimize the length of longest path between any two vertices in the resulting graph.

• $\mathrm{■}$

  We may want to minimize the area of the largest face, or maximize the area of the smallest face.

In general, even satisfying the first property alone is already NP-hard. However, this is not the case when there is only a single type of tile. Can we parametrize this problem by the number and/or complexity of the tiles? And for really simple sets of tiles, how many of these properties can we still test for efficiently?

The following variants and limitations might also be interesting to consider, and may influence to complexity of the problem.

• $\mathrm{■}$

  One can consider the tiles to be arranged into different shapes.

  • –

    A square

  • –

    A rectangle

  • –

    A polygon without holes

  • –

    A polygon with holes

  • –

    …

• $\mathrm{■}$

  For the boundary of the form (where tiles do not meet other tiles and so are not restricted by having to match another tile) we can …

  • –

    allow everything.

  • –

    prescribe something (natural would be that all are empty or all have a path going in or there is a prescription for each).

  • –

    avoid having a boundary by putting the tiles on a torus.

  • –

    …

• $\mathrm{■}$

  Restrictions on the graph other than (or in addition to) connectedness could also be made. For example, one could require the graph to be a tree.

During the seminar, we considered the following setting: Given $n^2$ tiles that have constantly many different types. Can all the tiles be arranged into one square such that the sides of the tiles match and the boundary is arbitrary?

When we restrict the tile types to the six types of tiles from Figure 3 and allow rotation, then if all tiles are of the same type, it is always possible to arrange them into a valid square. If tiles are of exactly two types, then we have polynomial time algorithms to decide if they can be arranged into a square. (For most combinations, the answer is always yes or always no.) For three types most cases still give easy polynomial time algorithms, but some cases are still open.

Let P be a polygonal domain with n vertices. A minlink path between points s,t in P is an s-t path with fewest edges (links). Computing the path is 3SUM-hard, and an $O(\sqrt{n})$ approximation can be found in subquadratic time [1]. Can a better approximation be computed in subaquatic time?

The following are sketches of ideas that arose during the seminar.

Alexander [1] proved that every knot or even link can be represented as a closed braid, that is, a braid with ends identified. This result is known as the Alexander theorem. The question is if this has a generalisation to knotted spheres in the following sense: Can every knotted 2-sphere in ${ℝ}^4$ be embedded sufficiently close to the standard symmetrically embedded 2-sphere ${𝕊}^2\subset {ℝ}^3\subset {ℝ}^4$ such that the closest point projection onto the symmetrically embedded 2-sphere is a local diffeomorphism? Has this question been answered before?

With the help of ChatGPT, Kristóf Huszár found the appropriate literature references, of which [2, Chapter 1] already contains this result with a pedagogical explanation.

A set $S$ of points in the plane is called universal with respect to a given drawing style and an integer $n$ if every graph on $n$ vertices admits a drawing in the given style such that the vertices are mapped to the points of $S$. For planar graphs, for example, the drawing style could require crossing-free straight-line edges. When considering drawings where the edges are circular arcs [1] or polygonal lines [4], the encoding of the edges may also need to be considered; for instance, a third point on an arc or the bends of a polygonal line. Also the number of edges can be a relevant parameter, which leads to the notion of universal geometric (or topological) graphs [2]. Another direction is to study universal point sets for restricted classes of planar graphs, such as planar 3-trees [3].