Converting between quadrilateral and standard solution sets in normal surface theory (Q1035322)

The theory of normal surfaces is crucial in algorithmic 3-manifold topology: introduced in [\textit{H. Kneser}, Jahresbericht D. M. V. 38, 248--260 (1929; JFM 55.0311.03)] and developed in [\textit{W. Haken}, Acta Math. 105, 245--375 (1961; Zbl 0100.19402), Math. Z. 80, 89--120 (1962; Zbl 0106.16605)], it plays a key role in algorithms concerning unknot recognition, 3-sphere recognition, JSJ decompositions and testing for incompressible surfaces (see for example [\textit{J. H. Rubinstein}, ``An algorithm to recognize the 3-sphere''. Chatterji, S. D. (ed.), Proceedings of the international congress of mathematicians, ICM '94, August 3-11, 1994, Zürich, Switzerland. Vol. I. Basel: Birkhäuser. 601--611 (1995; Zbl 0864.57009) and ``Polyhedral minimal surfaces, Heegaard splittings and decision problems for 3-dimensional manifolds''. Kazez, William H. (ed.), Geometric topology. 1993 Georgia international topology conference, August 2--13, 1993, Athens, GA, USA. Providence, RI: American Mathematical Society. AMS/IP Stud. Adv. Math. 2(pt.~1), 1--20 (1997; Zbl 0889.57021), \textit{A. Thompson}, Math. Res. Lett. 1, No.~5, 613--630 (1994; Zbl 0849.57009), \textit{W. Jaco} and \textit{J. L. Tollefson}, Ill. J. Math. 39, No.~3, 358--406 (1995; Zbl 0858.57018), \textit{W. Jaco} and \textit{U. Oertel}, Topology 23, 195--209 (1984; Zbl 0545.57003)]). Enumeration of normal surfaces for a triangulation containing \(n\) tetrahedra is very slow, since it involves a polytope vertex enumeration in a \(7n\)-dimensional vector space, by means of the so called \textit{standard coordinates}. Tollefson's Q-theory about \textit{quadrilateral coordinates} (see [\textit{J. L. Tollefson}, Pac. J. Math. 183, No.~2, 359--374 (1998; Zbl 0930.57017)]) speeds up the operation, by working in a \(3n\)-dimensional vector space; however, the quadrilateral solution set is in general a proper subset of the standard one. In the present paper, the author presents algorithms for converting the standard solution set into the quadrilateral one, and vice versa. As a consequence, a new way of enumerating all vertex normal surfaces in standard coordinates (by going via quadrilateral ones) is obtained, yielding both the speed of quadrilateral coordinates and the wider applicability of standard coordinates. Experimentation with the software package \textit{Regina}, see the author's paper [Exp. Math. 13, No.~3, 267--272 (2004; Zbl 1090.57003)], shows this new algorithm to be extremely fast in practice, improving speed for large cases by factors from \(10^3\) to \(10^6\).