Computational topology

Algorithmic topology, or computational topology, is a subfield of topology with an overlap with areas of computer science, in particular computational geometry and computational complexity theory.

A primary concern of algorithmic topology, as its name suggests, is to develop efficient algorithms for solving topological problems, or using topological methods to solve algorithmic problems from other fields.

Major algorithms by subject area

Algorithmic 3-manifold theory

A large family of algorithms concerning 3-manifolds revolve around normal surface theory, which is a phrase that encompasses several techniques to turn problems in 3-manifold theory into integer linear programming problems.

• Rubinstein and Thompson's 3-sphere recognition algorithm. This is an algorithm that takes as input a triangulated 3-manifold and determines whether or not the manifold is homeomorphic to the 3-sphere. It has exponential run-time in the number of tetrahedra in the initial 3-manifold, and also an exponential memory profile, moreover, it is implemented in the software package Regina.^[1] Saul Schleimer went on to show the problem lies in the complexity class NP.^[2]

• The connect-sum decomposition of 3-manifolds is also implemented in Regina, has exponential run-time and is based on a similar algorithm to the 3-sphere recognition algorithm.

• Determining that the Seifert-Weber 3-manifold contains no incompressible surface has been algorithmically implemented by Rubinstein, Tillmann and Burton ^[3] and based on normal surface theory.

• The Manning algorithm is an algorithm to find hyperbolic structures on 3-manifolds whose fundamental group have a solution to the word problem.^[4]

At present the JSJ decomposition has not been implemented algorithmically in computer software. Neither has the compression-body decomposition. There are some very popular and successful heuristics, such as SnapPea which has much success computing approximate hyperbolic structures on triangulated 3-manifolds. It is known that the full classification of 3-manifolds can be done algorithmically.^[5]

Conversion Algorithms

• SnapPea implements an algorithm to convert a planar knot or link diagram into a cusped triangulation. This algorithm has a roughly linear run-time in the number of crossings in the diagram, and low memory profile. The algorithm is similar to the Wirthinger algorithm for constructing presentations of the fundamental group of link complements given by planar diagrams. Similarly, SnapPea can convert surgery presentations of 3-manifolds into triangulations of the presented 3-manifold.

• D.Thurston and F.Costantino have a procedure to construct a triangulated 4-manifold from a triangulated 3-manifold. Similarly, it can be used to construct surgery presentations of triangulated 3-manifolds, although the procedure is not explicitly written as an algorithm in principle it should have polynomial run-time in the number of tetrahedra of the given 3-manifold triangulation.^[6]

• S. Schleimer has an algorithm which produces a triangulated 3-manifold, given input a word (in Dehn twist generators) for the mapping class group of a surface. The 3-manifold is the one that uses the word as the attaching map for a Heegaard splitting of the 3-manifold. The algorithm is based on the concept of a layered triangulation.

Algorithmic knot theory

• Determining whether or not a knot is trivial is known to be in the complexity class NP ^[7]

• The problem of determining the genus of a knot is known to have complexity class PSPACE.

• There are polynomial-time algorithms for the computation of the Alexander polynomial of a knot.^[8]

Computational homotopy

• Computational methods for homotopy groups of spheres.
• Computational methods for solving systems of polynomial equations.
• Brown has an algorithm to compute the homotopy groups of spaces that are finite Postnikov complexes,^[9] although it is not widely considered implementable.

See also

• Computational geometry
• Digital topology
• Topological data analysis
• Spatial-temporal reasoning
• Experimental mathematics

References

1. ^ B.~Burton. Introducing Regina, the 3-manifold topology software, Experimental Mathematics 13 (2004), 267–272.
2. ^ http://www.warwick.ac.uk/~masgar/Maths/np.pdf
3. ^ J. Hyam Rubinstein, Stephan Tillmann, Ben Burton. No other proof exists. To appear in Transactions of the American Mathematical Society, arXiv:0909.4625, September 2009.
4. ^ J.Manning, Algorithmic detection and description of hyperbolic structures on 3-manifolds with solvable word problem, Geometry and Topology 6 (2002) 1--26
5. ^ S.Matveev, Algorithmic topology and the classification of 3-manifolds, Springer-Verlag 2003
6. ^ F. Costantino, D.Thurston. 3-manifolds efficiently bound 4-manifolds. Journal of Topology 2008 1(3):703-745
7. ^ "The computational complexity of knot and link problems" by Joel Hass, Jeffrey Lagarias, and Nicholas Pippenger [Journal of the ACM 46(2) 185-211 (1999)]
8. ^ http://katlas.math.toronto.edu/wiki/Main_Page
9. ^ E H Brown's "Finite Computability of Postnikov Complexes" annals of Mathematics (2) 65 (1957) pp 1-20

External links

• CompuTop software archive
• Workshop on Application of Topology in Science and Engineering
• Computational Topology at Stanford University

Books

• Tomasz Kaczynski, Konstantin Mischaikow, Marian Mrozek (2004). Computational Homology. Springer. ISBN 0-387-40853-3. http://books.google.com/books?id=AShKtpi3GecC. 
• Afra J. Zomorodian (2005). Topology for Computing. Cambridge. ISBN 0-521-83666-2. http://books.google.com/books?id=oKEGGMgnWKcC. 
• Computational Topology: An Introduction, Herbert Edelsbrunner, John L. Harer, AMS Bookstore, 2010, ISBN 978-0-8218-4925-5