The complexity of the normal surface solution space

DOI10.1145/1810959.1810995MaRDI QIDQ5405883zbMATH OpenOpenAlexFDO

Authors Benjamin A. Burton

Publication date 3 April 2014

Published in Proceedings of the twenty-sixth annual symposium on Computational geometry (Search for Journal in Brave)

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

zbMATH Keywords

3-manifoldscomplexitycomputational topologynormal surfacesvertex enumeration

Mathematics Subject Classification ID

Geometric constructions in real or complex geometry (51M15) Topological manifolds (57N99) Triangulating manifolds (57Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Normal surface theory is a central tool in algorithmic three-dimensional topology, and the enumeration of vertex normal surfaces is the computational bottleneck in many important algorithms. However, it is not well understood how the number of such surfaces grows in relation to the size of the underlying triangulation. Here we address this problem in both theory and practice. In theory, we tighten the exponential upper bound substantially; furthermore, we construct pathological triangulations that prove an exponential bound to be unavoidable. In practice, we undertake a comprehensive analysis of millions of triangulations and find that in general the number of vertex normal surfaces is remarkably small, with strong evidence that our pathological triangulations may in fact be the worst case scenarios. This analysis is the first of its kind, and the striking behaviour that we observe has important implications for the feasibility of topological algorithms in three dimensions.

Recommendations

• Computational topology and normal surfaces: theoretical and experimental complexity bounds
• Maximal admissible faces and asymptotic bounds for the normal surface solution space
• Optimizing the double description method for normal surface enumeration
• Enumerating fundamental normal surfaces: Algorithms, experiments and invariants
• On the complexity of immersed normal surfaces

Cited in

(13)

• Converting between quadrilateral and standard solution sets in normal surface theory
• Maximal admissible faces and asymptotic bounds for the normal surface solution space
• On the complexity of immersed normal surfaces
• Quadrilateral–Octagon Coordinates for Almost Normal Surfaces
• The Weber-Seifert dodecahedral space is non-Haken
• Core curves of triangulated solid tori
• Optimizing the double description method for normal surface enumeration
• Why happy instead of just normal?
• Computational topology and normal surfaces: theoretical and experimental complexity bounds
• Tracing compressed curves in triangulated surfaces
• The computational complexity of classical knot recognition
• 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: The complexity of the normal surface solution space

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