A Fast Octree-Based Algorithm for Computing Ropelength

Details A Fast Octree-Based Algorithm for Computing Ropelength A Fast Octree-Based Algorithm for Computing Ropelength

2004-09-21

arxiv.org/abs/math/0409416v2

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-442563