Compressed data structures for Heegaard splittings
Henrique Ennes and Clément Maria
Heegaard 分裂通过将处理方式粘合在一起,为封闭的三流形提供了自然表示。 这些分裂可以等价于两个有限的经络躺在表面,它定义了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 ca...