School Seminars and Colloquia

The feasibility of algorithms in 3-manifold topology

Algebra/Geometry/Topology Seminar

by Ben Burton


Institution: U. Queensland
Date: Mon 21st December 2009
Time: 2:15 PM
Location: Sisalkraft Theatre, Architecture

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. We finish with a startling observation in which the statistical distribution of the vertex surface count does not appear to grow at all.

For More Information: craigw@ms.unimelb.edu.au