Compressed Data Structures for Heegaard Splitting

We assume the reader is acquainted with the basic notions of surface theory at the level of [25], referring to the paper’s full version for details. We use $\mathrm{\Sigma }$ to denote a general surface and ${\mathrm{\Sigma }}_g$ the (unique) closed surface of genus $g$. Whenever possible, we reserve Greek letters for multicurves and Latin letters for curves and arcs. All (multi)curves are assumed simple. As usual, we do not differentiate (multi)curves from their isotopy classes if no confusion arises.

The mapping class group of the surface ${\mathrm{\Sigma }}_g$, $\mathrm{Mod}({\mathrm{\Sigma }}_g)$, is the group of orientation-preserving ${\mathrm{\Sigma }}_g\to {\mathrm{\Sigma }}_g$ homeomorphisms up to isotopy. For each $g$, $\mathrm{Mod}({\mathrm{\Sigma }}_g)$ is finitely generated as a group by an alphabet $ℒ$, consisting of Dehn twists about $3g-1$ (isotopy classes of) canonically defined essential curves $s_1,\mathrm{\dots },s_{3g-1}$ [43]. Formally, a Dehn twist ${\tau }_s:{\mathrm{\Sigma }}_g\to {\mathrm{\Sigma }}_g$ about $s$ is given by cutting out a cylindrical regular neighborhood around the curve, applying a $2\pi$ left-twist to one of the cylinder’s boundaries, and gluing the cylinder back into the surface. We call the curves $s_1,\mathrm{\dots },s_{3g-1}$ the surface’s Lickorish generators. Hopefully without confusion, we also call the Dehn twists in the alphabet $ℒ=\{{\tau }_{s_1},\mathrm{\dots },{\tau }_{s_{3g-1}}\}$ Lickorish generators.

An essential multicurve $\gamma$ in ${\mathrm{\Sigma }}_g$ is a system if ${\mathrm{\Sigma }}_g$ cut along $\gamma$, ${\mathrm{\Sigma }}_g\backslash \gamma$, is a $2g$ punctured sphere. A system $\gamma$ in ${\mathrm{\Sigma }}_g$ can be used to construct the genus $g$ handlebody ${\mathscr{H}}_{\gamma }$ where we attach 2-handles along the curves $\gamma$ in $\mathrm{\Sigma }\times \{0\}$ and fill any spherical boundary component with 3-handles. Note that $\partial {\mathscr{H}}_{\gamma }={\mathrm{\Sigma }}_g$ and that ${\mathscr{H}}_{\gamma }$ is homeomorphic to the direct sum of $g$ solid tori. Components of $\gamma$ are meridians of ${\mathscr{H}}_{\gamma }$ in the sense that they bound disks in the handlebody’s interior. Two systems $\gamma$ and ${\gamma }^{\prime }$ in ${\mathrm{\Sigma }}_g$ will be called equivalent if ${\gamma }^{\prime }$ is a set of meridians in ${\mathscr{H}}_{\gamma }$ (which implies that $\gamma$ is a set of meridians in ${\mathscr{H}}_{{\gamma }^{\prime }}$).

Let $c_1,c_2$ be two components of a system $\gamma$ and $p$ an arc from a puncture corresponding to $c_1$ to a puncture corresponding to $c_2$ in ${\mathrm{\Sigma }}_g\backslash \gamma$. The band sum of $c_1,c_2$ and $p$ is the curve $c$ in ${\mathrm{\Sigma }}_g\backslash \gamma$ obtained by the surgery of Figure 1. One can show that $c$ is a meridian in ${\mathscr{H}}_{\gamma }$ [22, 37], so ${\gamma }^{\prime }=\gamma -\{c_1\}\cup \{c\}$ is a system equivalent to $\gamma$. We call this whole operation a disk slide. With finitely many applications of disk slides and isotopies, a system $\gamma$ can be transformed into any equivalent system ${\gamma }^{\prime }$ [37].

A genus $g$ Heegaard splitting is the closed 3-manifold resulting from the gluing of two handlebodies with boundaries homeomorphic to ${\mathrm{\Sigma }}_g$ through a gluing map $f:{\mathrm{\Sigma }}_g\to {\mathrm{\Sigma }}_g$. In fact, one might assume that $f$ is given by a $\varphi \in \mathrm{Mod}({\mathrm{\Sigma }}_g)$ composed with some canonical orientation-reversing homeomorphism. This means that a Heegaard splitting can be represented by a pair $({\mathrm{\Sigma }}_g,\varphi )$ where $\varphi$ is a word on Lickorish generators. We call this pair the Heegaard word for the splitting. Every closed 3-manifold has a Heegaard splitting [46, 47].

Note that if we fix a system of meridians $\alpha$ on one of the two handlebodies, ${\mathscr{H}}_{\alpha }$, then $\beta =\varphi (\alpha )$ is a system of meridians of the other handlebody, ${\mathscr{H}}_{\beta }$. We call the tuple $({\mathrm{\Sigma }}_g,\alpha ,\beta )$ a Heegaard diagram. Heegaard diagrams are algorithmically independent of words: any two systems $\alpha$ and $\beta$ will define the same splitting, provided that the curves are meridians in their respective handlebodies. Diagrams are therefore not unique for a given splitting. For example, if $\beta$ and ${\beta }^{\prime }$ are isotopic diagrams on ${\mathrm{\Sigma }}_g$ – that is, $\beta$ and ${\beta }^{\prime }$ are isotopic multicurves in ${\mathrm{\Sigma }}_g$ – then $({\mathrm{\Sigma }}_g,\alpha ,\beta )$ and $({\mathrm{\Sigma }}_g,\alpha ,{\beta }^{\prime })$ define the same manifold. Similarly, if $\beta$ is equivalent to ${\beta }^{\prime }$, we say that the diagrams are equivalent and $({\mathrm{\Sigma }}_g,\alpha ,\beta )$ and $({\mathrm{\Sigma }}_g,\alpha ,{\beta }^{\prime })$ also define the same 3-manifold. In this sense, disk slides play for Heegaard diagrams a role similar to the Reidemeister moves for knots.

A splitting $({\mathrm{\Sigma }}_g,{\mathscr{H}}_{\alpha },{\mathscr{H}}_{\beta })$ is reducible if there is a curve $c$ in ${\mathrm{\Sigma }}_g$ that is a meridian of both ${\mathscr{H}}_{\alpha }$ and ${\mathscr{H}}_{\beta }$. We call a diagram $({\mathrm{\Sigma }}_g,\alpha ,\beta )$ reducible if either (1) there is a component $a\in \alpha$ and a component $b\in \beta$ that are isotopic in ${\mathrm{\Sigma }}_g$; or (2) there is a separating curve $s$, disjoint from both $\alpha$ and $\beta$, and such that ${\mathrm{\Sigma }}_g\backslash s$ defines a connected sum of two Heegaard splittings of smaller genera. The uniqueness of fundamental group decomposition [3] and [51][Theorem 6.3.5] imply that a reducible diagram represents a reducible splitting. A reducible splitting can always be written as the connected sum of sub-splittings [3, 37].

A presentation $⟨x_1,\mathrm{\dots },x_g|r_1,\mathrm{\dots },r_g⟩$ of the fundamental group ${\pi }_1(M)$ can be obtained as follows [30, 37]: label the curves $a_1,\mathrm{\dots },a_g\in \alpha$ and $b_1,\mathrm{\dots },b_g\in \beta$ and give them an orientation; then traverse each curve $b_i$ along the assumed orientation and, whenever it intersects some $a_j$, we append $x_j$ to the relation $r_i$ if the index of the intersection is positive, otherwise we append $x_j^{-1}$ to it. Because the first (integral) homology group of $M$, $H_1(M)$ is the abelianization of ${\pi }_1(M)$ [28], we can present $H_1(M)$ as $⟨x_1,\mathrm{\dots },x_g|r_1^{\prime },\mathrm{\dots },r_g^{\prime },[x_i,x_j]⟩$, where each $r_i^{\prime }=x_1^{k_i^1}\mathrm{\dots }{x}_g^{k_i^g}$ can be computed by commuting the generators $x_j$ in the relations $r_i$. Note that $k_i^j$ equals the algebraic intersection number $\widehat{i}(b_i,a_j)$ and we store this information in a $g\times g$ presentation matrix for $H_1(M)$, whose Smith normal form carries all the necessary information of the homology group.

Heegaard diagrams consist of three essential components that any candidate data structure must encode: a surface, ${\mathrm{\Sigma }}_g$, and two multicurves, $\alpha$ and $\beta$. Starting with the surface, a graph $T=(V,E)$ embedded in $\mathrm{\Sigma }$ is a cellular embedding if the manifold defined by cutting $\mathrm{\Sigma }$ along $T$, $\mathrm{\Sigma }\backslash T$, is homeomorphic to a collection of disks. We call each component of $\mathrm{\Sigma }\backslash T$ a face of $T$. A cellular embedding $T$ in the surface $\mathrm{\Sigma }$ is said to be oriented if we assign to each face an ordered list of its vertices, consistent with the orientation of $\mathrm{\Sigma }$ as in the right-hand rule. We assume every cellular embedding to be oriented. A cellular embedding $T$ is a (generalized) triangulation of $\mathrm{\Sigma }$ if exactly three edges of $T$ bound each face. We define the size of a triangulation, $|T|$, as the number of faces; note that $|V|,|E|=O(|T|)$ where $|V|$ is the number of vertices of the triangulation and $|E|$ is the number of edges. Surface triangulations are not to be confused with the similar concept of 3-manifold triangulations.

Every oriented surface can be described as a data structure by a triangulation. For the triangulations themselves, we assume that they are given as a set of vertices, edges, and triangles, with bidirectional pointers between vertices and edges, and between edges and the triangles, therefore requiring a total space of $O(|T|)$. In particular, determining whether two triangles are adjacent, getting the incident vertices and edges of a triangle, and finding triangles bounded by a specific edge take constant time. Other, more compact data structures for triangulation, such as CGAL’s [20], can be converted into our structure in time $O(|T|)$ and at a similar cost to memory. More general cellular embeddings are treated similarly.

A curve $c$ is edged with respect to $T$ if it is disjoint from its faces. We represent an edged curve as a data structure by the list $E_T(c)=\{e\in E:|c\cap e|=e\}$, assumed to be ordered according to an implicit traversing orientation of $c$. Similarly, a multicurve $\gamma$ can be represented by a set of $\mathrm{\#}\gamma$ edge lists, one for each component, which we denote as $E_T(\gamma )$. We assume that no two components can share an edge, nor can the same component be incident to a vertex more than once; nevertheless, two distinct components can share a vertex. The complexity of $E_T(\gamma )$ is $\Vert E_T(\gamma )\Vert ={\sum }_{c\in \gamma }|E_T(c)|$.

On the other hand, a multicurve $\gamma$ is called standard in $T$ if it intersects the graph only at the edges and transversely. If $\gamma$ is standard, we represent it as a collection of words in a finite alphabet: arbitrarily orient the edges $E$ and take $E^{\pm }=E\cup E^{-1}$ for the letters. Then for each component $c$ of $\gamma$, the word $I_T(c)$ in ${(E^{\pm })}^{\ast }$ is given by traversing $c$ along some arbitrary direction and, whenever we intersect an edge $e\in E$, we append $e^i$ to $I_T(c)$ where $i$ is the index of the intersection. An intersection sequence representation for $\gamma$, $I_T(\gamma )$, is the set ${\{I_T(c)\}}_{c\in \gamma }$. While $E_T(\gamma )$ is well defined at the multicurve level, intersection sequences are defined only up to isotopies inside the cellular embedding’s faces. Moreover, cyclic permutations and taking inverses of the words $I_T(c)$ in $I_T(\gamma )$ define the same isotopy classes.

Instead of working with explicit intersection sequences, we will often assume straight line programs (SLPs) to express $I_T(c)$. Formally, an SLP on the alphabet $E^{\pm }$ is a finite sequence of equations $[x_1={\text{EXPR}}_1,\mathrm{\dots },x_{\mathrm{\ell }}={\text{EXPR}}_{\mathrm{\ell }}]$, where the left-hand side, $x_i$, are symbols not in $E^{\pm }$ called variables, and the expressions on the right-hand side, ${\text{EXPR}}_i\in {(E^{\pm }\cup \{x_1,\mathrm{\dots },x_{i-1}\})}^{\ast }$, are called assignments. Each assignment ${\text{EXPR}}_i$ is assumed to be a symbol from $E^{\pm }$, in which case the assignment is called simple, or of the form ${\text{EXPR}}_i=x_{j_1}^{\pm 1}\cdot x_{j_2}^{\pm 1}\cdot \mathrm{\cdots }\cdot x_{j_k}^{\pm 1}$, where , in which case we say the assignment is proper. In particular, the SLP $[x_1,\mathrm{\dots },x_{\mathrm{\ell }}]$ represents a word $w$ in ${(E^{\pm })}^{\ast }$ if recursively substituting the appropriate $x_j$ in each proper assignment, gives $x_{\mathrm{\ell }}$ equal to $w$. We call $\mathrm{\ell }$ the length of the SLP and define its complexity $m={\sum }_{i=1}^{\mathrm{\ell }}|{\text{EXPR}}_i|$, where $|{\text{EXPR}}_i|$ is the number of variables and symbols in the assignment $|{\text{EXPR}}_i|$. Given any word $e_1\mathrm{\dots }{e}_n$ in ${(E^{\pm })}^{\ast }$, one can trivially build an SLP of complexity $2n$, but there are instances in which SLPs can be used to give exponential gains over uncompressed representation of words [49]. Nonetheless, even in extremely compressed cases, several useful operations can still be efficiently performed, as stated in the following lemma, proved in the paper’s full version. Here and throughout, we assume that $\lg k$ is the number of bits necessary to represent the potentially signed integer $k$; in particular, $\lg k=\log k+2$ if $k$ is signed and $\log k+1$ if unsigned.

We will assume that every intersection sequence $I_T(c)$ is given by an SLP of complexity $\Vert I_T(c)\Vert$ and let $\Vert I_T(\gamma )\Vert ={\sum }_{c\in \gamma }\Vert I_T(c)\Vert$.

Now, suppose that $T=(V,E)$ is a triangulation. A standard (multi)curve $\gamma$ is normal if it intersects each face of $T$ in elementary arcs that connect distinct sides of the triangle in which they are contained. Equivalently, $\gamma$ is normal if each (uncompressed) intersection sequence in $I_T(\gamma )$ is cyclic reduced, that is, if there are no substrings of type $e{e}^{-1}$ or $e^{-1}e$ in any of the cyclic permutations of the components’ sequences. When the curve $c$ is normal for a triangulation, its isotopy class is fixed by the number of times it intersects each labeled edge [48], implying that we can describe it through a vector in $N_T(c)$ in ${\mathbb{N}}^{|E|}$. We call $N_T(c)$ the curve’s normal coordinates, whose complexity, $\Vert N_T(c)\Vert$, is the number of bits necessary to store this vector, i.e., ${\sum }_{e\in E}\lg e(c)={\sum }_{e\in E}(\log e(c)+1)$. Naturally, we define $N_T(\gamma )$ as the set ${\{N_T(c)\}}_{c\in \gamma }$.

Any normal (multi)curve $\gamma$ partitions the edges of $T$ into segments called ports. The overlay graph of $\gamma$ is defined by having as vertices the union of $V$ and the intersections $E\cap \gamma$, and as edges the union of the ports and the elementary arcs of $\gamma$ (see Figure 2). The overlay graph splits each triangle $t$ of the original triangulation into two types of regions: junctions, which are adjacent to three edges of $T$, and blocks, which are adjacent to only two. A port of the overlay graph is called redundant if it separates blocks. Following Erickson and Nayyeri [24], we define the street complex of $\gamma$, $S(T,\gamma )$, by deleting redundant ports and their endpoints from the overlay graph. In practice, the street complex merges blocks into longer faces called streets; naturally, $S(T,\gamma )$ is a cellular embedding in the surface triangulated by $T$, see Figure 2. We define the crossing sequence of a street in $S(T,\gamma )$ as the intersection sequence of a curve that crosses the street from one end to the other with respect to the original triangulation $T$. For simplicity, we assume that any port that separates two junctions is a degenerate street with a crossing sequence of length 1. The street complexes of all multicurves in this paper will have complexity $O(|T|)$ [24].

Heegaard splittings over the genus 1 surface – i.e., the torus – form the well-known family of lens spaces. Every lens space is uniquely given by a pair of integers $L(p,q)$, which, for a Heegaard splitting $({\mathrm{\Sigma }}_g,a,b)$, represents the algebraic intersection numbers of $b$ with the usual longitude and meridian of the torus (there is some ambiguity in the values of $p,q$, see [47]). A Dehn twist about the meridian $m$ of the torus maps $(p,q)$ to $(p+q,q)$, while about the longitude $\mathrm{\ell }$ maps to $(p,q-p)$. This gives a representation of $\mathrm{Mod}({\mathrm{\Sigma }}_1)$ in ${\mathbb{Z}}^2$ from which the homology of the Heegaard splitting $({\mathrm{\Sigma }}_g,\varphi )$ can be exactly computed by $|\varphi |$ matrix multiplications and one query on the final value of $q$. We used this approach to benchmark the accuracy of our method, which returned the expected $H_1$ for input words $\varphi$ of length up to 1000, the maximum size we tested.

Figure 5 compares the average computational time needed to find $H_1({\mathrm{\Sigma }}_1,\varphi )$ taken by our method and by Twister for four different families of $\varphi$ indexed by an integer $n$: (a) words of form ${({\tau }_m{\tau }_{\mathrm{\ell }}^{-1})}^n$; (b) uniformly sampled words of length $n$; (c) words of form ${\tau }_{\mathrm{\ell }}^n$; and (d) words of form ${\tau }_{\mathrm{\ell }}^n$, but this time, given in power-notation form. Averages were taken over 30 repetitions. In all cases, we compared our times with Twister’s with and without optimization (where, by optimization, the authors mean the greedy folding of tetrahedra; refer to their documentation for details¹¹1Available at https://snappy.computop.org.). Although optimization drastically reduces computational time, it seems to increase numerical error. In every instance, except for (d), we first transformed the words into a power-notation form before using them to compute $I_T(b)$; in total, this can be done in linear time on $|\varphi |$.

Case (a) is where our advantages compared to Twister are the worst. This is because the words ${({\tau }_m{\tau }_{\mathrm{\ell }}^{-1})}^n$ do not admit a non-trivial power-notation form, which is mainly responsible for our gains in the other cases. Nevertheless, it is worth highlighting that, while Twister is partially implemented in C++, our code is fully python. Case (b) represents the average case of computing the homology of lens spaces given a gluing map $\varphi$. We notice that we are now consistently faster for all values of $n$ tested. This happens exactly as we explore redundancies by first putting the word in power-notation form, with significant gains every time the same Dehn twist occurs in sequence (since $\mathrm{Mod}({\mathrm{\Sigma }}_g)$ has two generators, this will be the case quite often). The gains due to repetitions are further highlighted in (c): while Twister is bound to take $O(n^c)$, for some $c>1$, to compute the homologies, our approach takes time $O(n+\lg n)$, where the linear dependence comes solely from compressing the inputs to power-notation. In fact, if we assume the words already in power-notation, we are exponentially faster than Twister, as shown in case (d).

We can actually explore our structure’s usage of power-notation to compute invariants of families of 3-manifolds that would necessarily require exponentially many tetrahedra to be represented. The minimum number of tetrahedra in a layered triangulation of a lens space $L(p,q)$ is ${\sum }_i(a_i)-1$, where $(a_0,\mathrm{\dots },a_k)$ is the continued fraction expansion of $q/p$ [34]. Moreover, [32, 35] discovered families of lens spaces – including the spaces defined by $p=2n,q=1$ and $p=4n,q=2n-1,n\ge 2$ – for which layered triangulations are minimal among all triangulations. So, for example, while the family $L(2^n,1)$ necessarily requires exponentially many tetrahedra to be represented, it can be encoded in linear space in our data structure. It seems natural to expect that there are many other families of manifolds, with diagrams exponentially smaller than the minimum number of tetrahedra, for which our techniques can provide real computational gains compared to any existing method.