Mathematics – Geometric Topology
Scientific paper
2009-11-30
SCG '10: Proceedings of the Twenty-Sixth Annual Symposium on Computational Geometry, ACM, 2010, pp. 201-209
Mathematics
Geometric Topology
Extended abstract (i.e., conference-style), 14 pages, 8 figures, 2 tables; v2: added minor clarifications
Scientific paper
10.1145/1810959.1810995
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.
No associations
LandOfFree
The complexity of the normal surface solution space does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The complexity of the normal surface solution space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The complexity of the normal surface solution space will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-444158