The complexity of the normal surface solution space

Burton, Benjamin A. (2010). The complexity of the normal surface solution space. In: Proceedings of the 2010 Annual Symposium on Computational Geometry. 26th ACM Symposium on Computational Geometry [SCG], Snowbird, Utah, U.S.A., (201-209). 13-16 June 2010. doi:10.1145/1810959.1810995

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
uq217166_combined_long.pdf HERDC combined - Not publicly available application/pdf 473.79KB 9

Author Burton, Benjamin A.
Title of paper The complexity of the normal surface solution space
Conference name 26th ACM Symposium on Computational Geometry [SCG]
Conference location Snowbird, Utah, U.S.A.
Conference dates 13-16 June 2010
Proceedings title Proceedings of the 2010 Annual Symposium on Computational Geometry   Check publisher's open access policy
Journal name Proceedings of the Twenty-Sixth Annual Symposium On Computational Geometry (scg'10)   Check publisher's open access policy
Place of Publication New York , U.S.A.
Publisher ACM (Association for Computing Machinery) Press
Publication Year 2010
Sub-type Fully published paper
DOI 10.1145/1810959.1810995
Open Access Status
ISBN 9781450300162
ISSN 1055-6257
Volume 2010
Start page 201
End page 209
Total pages 9
Collection year 2011
Language eng
Abstract/Summary Normal surface theory is a central tool in algorithmic threedimensional 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 nd 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 rst of its kind, and the striking behaviour that we observe has important implications for the feasibility of topological algorithms in three dimensions.
Subjects E1
01 Mathematical Sciences
Keyword Computational topology
normal surfaces
vertex enumeration
Q-Index Code E1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Conference Paper
Collections: School of Mathematics and Physics
Official 2011 Collection
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 2 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 11 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Sun, 26 Sep 2010, 00:08:12 EST