The Least Spanning Area of a Knot and the Optimal Bounding Chain Problem
Abstract
Two fundamental objects in knot theory are the minimal genus surface and the least area surface bounded by a knot in a 3dimensional manifold. When the knot is embedded in a general 3manifold, the problems of finding these surfaces were shown to be NPcomplete and NPhard respectively. However, there is evidence that the special case when the ambient manifold is R^3, or more generally when the second homology is trivial, should be considerably more tractable. Indeed, we show here that a natural discrete version of the least area surface can be found in polynomial time. The precise setting is that the knot is a 1dimensional subcomplex of a triangulation of the ambient 3manifold. The main tool we use is a linear programming formulation of the Optimal Bounding Chain Problem (OBCP), where one is required to find the smallest norm chain with a given boundary. While the decision variant of OBCP is NPcomplete in general, we give conditions under which it can be solved in polynomial time. We then show that the least area surface can be constructed from the optimal bounding chain using a standard desingularization argument from 3dimensional topology. We also prove that the related Optimal Homologous Chain Problem is NPcomplete for homology with integer coefficients, complementing the corresponding result of Chen and Freedman for mod 2 homology.
 Publication:

arXiv eprints
 Pub Date:
 December 2010
 arXiv:
 arXiv:1012.3030
 Bibcode:
 2010arXiv1012.3030D
 Keywords:

 Computer Science  Computational Geometry;
 Computer Science  Data Structures and Algorithms;
 Mathematics  Differential Geometry;
 Mathematics  Geometric Topology;
 57M35;
 57M25;
 49Q05;
 68U05;
 F.2.2;
 G.1.6
 EPrint:
 9 pages, 5 figures. V2: Added Remark 5.7. V3: Many minor improvements. To appear in SoCG 2011