Mathematics – Geometric Topology
Scientific paper
2011-07-12
Mathematics
Geometric Topology
19 pages, 7 figures, 1 table; v2: minor revisions; to appear in ACM Transactions on Mathematical Software
Scientific paper
The crosscap number of a knot is an invariant describing the non-orientable surface of smallest genus that the knot bounds. Unlike knot genus (its orientable counterpart), crosscap numbers are difficult to compute and no general algorithm is known. We present three methods for computing crosscap number that offer varying trade-offs between precision and speed: (i) an algorithm based on Hilbert basis enumeration and (ii) an algorithm based on exact integer programming, both of which either compute the solution precisely or reduce it to two possible values, and (iii) a fast but limited precision integer programming algorithm that bounds the solution from above. The first two algorithms advance the theoretical state of the art, but remain intractable for practical use. The third algorithm is fast and effective, which we show in a practical setting by making significant improvements to the current knowledge of crosscap numbers in knot tables. Our integer programming framework is general, with the potential for further applications in computational geometry and topology.
Burton Benjamin A.
Ozlen Melih
No associations
LandOfFree
Computing the crosscap number of a knot using integer programming and normal surfaces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Computing the crosscap number of a knot using integer programming and normal surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing the crosscap number of a knot using integer programming and normal surfaces will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-566171