Enumerating fundamental normal surfaces: Algorithms, experiments and invariants

DOI10.1137/1.9781611973198.11MaRDI QIDQ5232496zbMATH OpenOpenAlexFDO

Authors Benjamin A. Burton

Publication date 12 September 2019

Published in 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.7055

Mathematics Subject Classification ID

General topology of 3-manifolds (57K30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Computational knot theory and 3-manifold topology have seen significant breakthroughs in recent years, despite the fact that many key algorithms have complexity bounds that are exponential or greater. In this setting, experimentation is essential for understanding the limits of practicality, as well as for gauging the relative merits of competing algorithms. In this paper we focus on normal surface theory, a key tool that appears throughout low-dimensional topology. Stepping beyond the well-studied problem of computing vertex normal surfaces (essentially extreme rays of a polyhedral cone), we turn our attention to the more complex task of computing fundamental normal surfaces (essentially an integral basis for such a cone). We develop, implement and experimentally compare a primal and a dual algorithm, both of which combine domain-specific techniques with classical Hilbert basis algorithms. Our experiments indicate that we can solve extremely large problems that were once though intractable. As a practical application of our techniques, we fill gaps from the KnotInfo database by computing 398 previously-unknown crosscap numbers of knots.

Recommendations

• Computational topology and normal surfaces: theoretical and experimental complexity bounds
• A numerical approach to the fundamental theorem of surfaces
• On the hardness of finding normal surfaces
• scientific article; zbMATH DE number 1008334
• scientific article; zbMATH DE number 1408277
• On the geometry of normalized surfaces
• The classification of surfaces via normal curves
• A first approach towards normal parametrizations of algebraic surfaces
• ON THE NORMAL PARAMETERIZATION OF CURVES AND SURFACES
• Computable invariants for curves and surfaces

Cited in

(8)

• Counting essential surfaces in \(3\)-manifolds
• Computing the crosscap number of a knot using integer programming and normal surfaces
• Computing closed essential surfaces in knot complements
• Computational topology and normal surfaces: theoretical and experimental complexity bounds
• The complexity of the normal surface solution space
• Slope norm and an algorithm to compute the crosscap number
• Effective computation of the Heegaard genus of 3-manifolds
• Totally geodesic surfaces in hyperbolic 3-manifolds: algorithms and examples

This page was built for publication: Enumerating fundamental normal surfaces: Algorithms, experiments and invariants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232496)