Optimizing the double description method for normal surface enumeration

Details Optimizing the double description method for normal surface enumeration Optimizing the double description method for normal surface enumeration

2008-08-29

arxiv.org/abs/0808.4050v3

Mathematics of Computation 79 (2010), no. 269, 453-484

Mathematics

Geometric Topology

27 pages, 12 figures; v2: Removed the 3^n bound from Section 3.3, fixed the projective equation in Lemma 4.4, clarified "most

Scientific paper

10.1090/S0025-5718-09-02282-0

Many key algorithms in 3-manifold topology involve the enumeration of normal surfaces, which is based upon the double description method for finding the vertices of a convex polytope. Typically we are only interested in a small subset of these vertices, thus opening the way for substantial optimization. Here we give an account of the vertex enumeration problem as it applies to normal surfaces, and present new optimizations that yield strong improvements in both running time and memory consumption. The resulting algorithms are tested using the freely available software package Regina.

Affiliated with

Also associated with

No associations

Rating

Optimizing the double description method for normal surface enumeration 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 Optimizing the double description method for normal surface enumeration, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimizing the double description method for normal surface enumeration will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-542608