Mathematics – Geometric Topology
Scientific paper
2009-01-17
Algebraic & Geometric Topology 9 (2009), 2121-2174
Mathematics
Geometric Topology
55 pages, 10 figures; v2: minor fixes only, plus a reformat for the journal style
Scientific paper
10.2140/agt.2009.9.2121
The enumeration of normal surfaces is a crucial but very slow operation in algorithmic 3-manifold topology. At the heart of this operation is a polytope vertex enumeration in a high-dimensional space (standard coordinates). Tollefson's Q-theory speeds up this operation by using a much smaller space (quadrilateral coordinates), at the cost of a reduced solution set that might not always be sufficient for our needs. In this paper we present algorithms for converting between solution sets in quadrilateral and standard coordinates. As a consequence we obtain a new algorithm for enumerating all standard vertex normal surfaces, yielding both the speed of quadrilateral coordinates and the wider applicability of standard coordinates. Experimentation with the software package Regina shows this new algorithm to be extremely fast in practice, improving speed for large cases by factors from thousands up to millions.
No associations
LandOfFree
Converting between quadrilateral and standard solution sets in normal surface theory 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 Converting between quadrilateral and standard solution sets in normal surface theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Converting between quadrilateral and standard solution sets in normal surface theory will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-119013