标题： 用于Heegaard分解的压缩数据结构 显示英文标题

标题： Compressed data structures for Heegaard splittings

摘要： Heegaard 分割通过沿着共同曲面粘合柄体，为闭合 3-流形提供了一种自然表示。 这些分割可以由位于曲面上的两个有限的圈线集合等价地给出，这定义了一个 Heegaard 图。 我们提出了一种数据结构，以有效地将 Heegaard 图表示为相对于曲面三角剖分的正常曲线，该曲面的复杂性由表达正常坐标向量所需的二进制空间来衡量。 与 3-流形的三角剖分相比，这种结构可以显著压缩，对于某些族来说可以实现指数级的增益。 即使在这样简洁的复杂度定义下，我们建立了多项式时间算法来比较和操作图，执行稳定化，检测平凡的稳定化和约简，并计算底层流形的拓扑不变量，例如它们的基本群和第一同调群。 我们还将我们技术的早期实现与标准的 3-流形软件程序进行了对比，在平均情况下实现了更好的精度和更快的算法，并且对于输入的一些特定表示，速度有指数级的提升。 显示英文摘要

摘要： Heegaard splittings provide a natural representation of closed 3-manifolds by gluing handlebodies along a common surface. These splittings can be equivalently given by two finite sets of meridians lying in the surface, which define a Heegaard diagram. We present a data structure to effectively represent Heegaard diagrams as normal curves with respect to triangulations of a surface of complexity measured by the space required to express the normal coordinates' vectors in binary. This structure can be significantly more compressed than triangulations of 3-manifolds, given exponential gains for some families. Even with this succinct definition of complexity, we establish polynomial time algorithms for comparing and manipulating diagrams, performing stabilizations, detecting trivial stabilizations and reductions, and computing topological invariants of the underlying manifolds, such as their fundamental and first homology groups. We also contrast early implementations of our techniques with standard software programs for 3-manifolds, achieving better precision and faster algorithms for the average cases and exponential gains in speed for some particular presentations of the inputs.