Algorithmic topology, or computational topology, is a subfield of topology with an overlap with areas of computer science, in particular,

computational geometry Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...

and computational complexity theory. A primary concern of algorithmic topology, as its name suggests, is to develop efficient algorithms for solving problems that arise naturally in fields such as

graphics Graphics () are visual images or designs on some surface, such as a wall, canvas, screen, paper, or stone, to inform, illustrate, or entertain. In contemporary usage, it includes a pictorial representation of data, as in design and manufacture ...

, robotics, structural biology and

chemistry Chemistry is the science, scientific study of the properties and behavior of matter. It is a natural science that covers the Chemical element, elements that make up matter to the chemical compound, compounds made of atoms, molecules and ions ...

, using methods from computable topology.

Major algorithms by subject area

Algorithmic 3-manifold theory

A large family of algorithms concerning

3-manifold In mathematics, a 3-manifold is a space that locally looks like Euclidean 3-dimensional space. A 3-manifold can be thought of as a possible shape of the universe. Just as a sphere looks like a plane to a small enough observer, all 3-manifolds lo ...

s revolve around

normal surface In mathematics, a normal surface is a surface inside a triangulated 3-manifold that intersects each tetrahedron so that each component of intersection is a ''triangle'' or a ''quad'' (see figure). A triangle cuts off a vertex of the tetrahedron wh ...

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 In trigonometry and geometry, triangulation is the process of determining the location of a point by forming triangles to the point from known points. Applications In surveying Specifically in surveying, triangulation involves only angle me ...

and determines whether or not the manifold is

homeomorphic In the mathematical field of topology, a homeomorphism, topological isomorphism, or bicontinuous function is a bijective and continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphi ...

to the

3-sphere In mathematics, a 3-sphere is a higher-dimensional analogue of a sphere. It may be embedded in 4-dimensional Euclidean space as the set of points equidistant from a fixed central point. Analogous to how the boundary of a ball in three dimensi ...

. It has exponential run-time in the number of tetrahedral simplexes in the initial 3-manifold, and also an exponential memory profile. Moreover, it is implemented in the software package Regina. Saul Schleimer went on to show the problem lies in the complexity class NP. Furthermore, Raphael Zentner showed that the problem lies in the complexity class coNP, provided that the generalized Riemann hypothesis holds. He uses instanton gauge theory, the geometrization theorem of 3-manifolds, and subsequent work of Greg Kuperberg on the complexity of knottedness detection. * 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 Burton, Rubinstein and Tillmann and based on normal surface theory. * The ''Manning algorithm'' is an algorithm to find hyperbolic structures on 3-manifolds whose

fundamental group In the mathematical field of algebraic topology, the fundamental group of a topological space is the group of the equivalence classes under homotopy of the loops contained in the space. It records information about the basic shape, or holes, of ...

have a solution to the word problem. 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.

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

of link complements given by planar diagrams. Similarly, SnapPea can convert

surgery Surgery ''cheirourgikē'' (composed of χείρ, "hand", and ἔργον, "work"), via la, chirurgiae, meaning "hand work". is a medical specialty that uses operative manual and instrumental techniques on a person to investigate or treat a pat ...

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. * 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 * 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.

Computational homotopy

* Computational methods for homotopy groups of spheres. * Computational methods for solving

systems of polynomial equations A system of polynomial equations (sometimes simply a polynomial system) is a set of simultaneous equations where the are polynomials in several variables, say , over some field . A ''solution'' of a polynomial system is a set of values for the s ...

. * Brown has an algorithm to compute the homotopy groups of spaces that are finite Postnikov complexes, although it is not widely considered implementable.

Computational homology

Computation of

homology group In mathematics, homology is a general way of associating a sequence of algebraic objects, such as abelian groups or modules, with other mathematical objects such as topological spaces. Homology groups were originally defined in algebraic topolog ...

s of cell complexes reduces to bringing the boundary matrices into Smith normal form. Although this is a completely solved problem algorithmically, there are various technical obstacles to efficient computation for large complexes. There are two central obstacles. Firstly, the basic Smith form algorithm has cubic complexity in the size of the matrix involved since it uses row and column operations which makes it unsuitable for large cell complexes. Secondly, the intermediate matrices which result from the application of the Smith form algorithm get filled-in even if one starts and ends with sparse matrices. * Efficient and probabilistic Smith normal form algorithms, as found in th
LinBox
library. * Simple homotopic reductions for pre-processing homology computations, as in th

software package. * Algorithms to compute persistent homology of filtered complexes, as in th
TDAstats
R package.

References

External links

CompuTop software archiveWorkshop on Application of Topology in Science and EngineeringComputational Topology at Stanford UniversityComputational Homology Software (CHomP) at Rutgers University

Computational Homology Software (RedHom) at Jagellonian University

The javaPlex Persistent Homology software at Stanford

PHAT: persistent homology algorithms toolbox

Books

* *
Computational Topology: An Introduction
Herbert Edelsbrunner, John L. Harer, AMS Bookstore, 2010, {{DEFAULTSORT:Computational Topology Applied mathematics Computational complexity theory Topology Computational fields of study