Mathematics – Differential Geometry
Scientific paper
2004-09-21
Mathematics
Differential Geometry
9 pages, 9 figures, post-refereeing version
Scientific paper
The ropelength of a space curve is usually defined as the quotient of its length by its thickness: the radius of the largest embedded tube around the knot. This idea was extended to space polygons by Eric Rawdon, who gave a definition of ropelength in terms of doubly-critical self-distances (local minima of the distance function on pairs of points on the polygon) and a function of the exterior angles of the polygon. A naive algorithm for finding the doubly-critical self-distances of an n-edge polygon involves comparing each pair of edges, and so takes O(n^2) time. In this paper, we describe an improved algorithm, based on the notion of octrees, which runs in O(n log n) time. The speed of the ropelength computation controls the performance of ropelength-minimizing programs such as Rawdon and Piatek's TOROS. An implementation of our algorithm is freely available under the GNU Public License.
Ashton Ted
Cantarella Jason
No associations
LandOfFree
A Fast Octree-Based Algorithm for Computing Ropelength 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 A Fast Octree-Based Algorithm for Computing Ropelength, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Fast Octree-Based Algorithm for Computing Ropelength will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-442563