Algorithmic topology - AbsoluteAstronomy.com

Algorithmic topology, or computational topology, is a subfield of topology

Topology

Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...

with an overlap with areas of computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, in particular computational geometry

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 are also considered to be part of computational...

and computational complexity theory

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

.

A primary concern of algorithmic topology, as its name suggests, is to develop efficient algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s for solving topological problems, or using topological methods to solve algorithmic problems from other fields.

Algorithmic 3-manifold theory

A large family of algorithms concerning 3-manifold

3-manifold

In mathematics, a 3-manifold is a 3-dimensional manifold. The topological, piecewise-linear, and smooth categories are all equivalent in three dimensions, so little distinction is made in whether we are dealing with say, topological 3-manifolds, or smooth 3-manifolds.Phenomena in three dimensions...

s revolve around normal surface

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 . A triangle cuts off a vertex of the tetrahedron while a quad separates pairs of vertices...

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
3-manifold
In mathematics, a 3-manifold is a 3-dimensional manifold. The topological, piecewise-linear, and smooth categories are all equivalent in three dimensions, so little distinction is made in whether we are dealing with say, topological 3-manifolds, or smooth 3-manifolds.Phenomena in three dimensions...

and determines whether or not the manifold is homeomorphic to the 3-sphere
3-sphere
In mathematics, a 3-sphere is a higher-dimensional analogue of a sphere. It consists of the set of points equidistant from a fixed central point in 4-dimensional Euclidean space...

. 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
Regina (program)
Regina is a suite of mathematical software for 3-manifold topologists. It focuses upon the study of 3-manifold triangulations and includes support for normal surfaces and angle structures.- Features :...

. Saul Schleimer went on to show the problem lies in the complexity class NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...

.

The connect-sum
Connected sum
In mathematics, specifically in topology, the operation of connected sum is a geometric modification on manifolds. Its effect is to join two given manifolds together near a chosen point on each...

decomposition of 3-manifolds is also implemented in Regina
Regina (program)
Regina is a suite of mathematical software for 3-manifold topologists. It focuses upon the study of 3-manifold triangulations and includes support for normal surfaces and angle structures.- Features :...

, 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 and based on normal surface theory.

The Manning algorithm is an algorithm to find hyperbolic structures on 3-manifolds whose fundamental group
Fundamental group
In mathematics, more specifically algebraic topology, the fundamental group is a group associated to any given pointed topological space that provides a way of determining when two paths, starting and ending at a fixed base point, can be continuously deformed into each other...

have a solution to the word problem
Word problem for groups
In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element...

.

At present the JSJ decomposition

JSJ decomposition

In mathematics, the JSJ decomposition, also known as the toral decomposition, is a topological construct given by the following theorem:The acronym JSJ is for William Jaco, Peter Shalen, and Klaus Johannson...

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

SnapPea

SnapPea is free software designed to help mathematicians, in particular low-dimensional topologists, study hyperbolic 3-manifolds. The primary developer is Jeffrey Weeks, who created the first version as part of his doctoral thesis, supervised by William Thurston. The latest version is 3.0d3...

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
SnapPea
SnapPea is free software designed to help mathematicians, in particular low-dimensional topologists, study hyperbolic 3-manifolds. The primary developer is Jeffrey Weeks, who created the first version as part of his doctoral thesis, supervised by William Thurston. The latest version is 3.0d3...

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.

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
Heegaard splitting
In the mathematical field of geometric topology, a Heegaard splitting is a decomposition of a compact oriented 3-manifold that results from dividing it into two handlebodies.-Definitions:...

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
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...

The problem of determining the genus of a knot is known to have complexity class PSPACE
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...

.

There are polynomial-time algorithms for the computation of the Alexander polynomial
Alexander polynomial
In mathematics, the Alexander polynomial is a knot invariant which assigns a polynomial with integer coefficients to each knot type. James Waddell Alexander II discovered this, the first knot polynomial, in 1923...

of a knot.

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
Postnikov system
In homotopy theory, a branch of algebraic topology, a Postnikov system is a way of constructing a topological space from its homotopy groups...

, although it is not widely considered implementable.

External links

Books

Computational Topology: An Introduction, Herbert Edelsbrunner, John L. Harer, AMS Bookstore, 2010, ISBN 978-0-8218-4925-5