The ropelength of a space curve is usually defined as the quotient of itslength by its thickness: the radius of the largest embedded tube around theknot. This idea was extended to space polygons by Eric Rawdon, who gave adefinition of ropelength in terms of doubly-critical self-distances (localminima of the distance function on pairs of points on the polygon) and afunction of the exterior angles of the polygon. A naive algorithm for finding the doubly-critical self-distances of an n-edgepolygon involves comparing each pair of edges, and so takes O(n^2) time. Inthis 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 controlsthe performance of ropelength-minimizing programs such as Rawdon and Piatek'sTOROS. An implementation of our algorithm is freely available under the GNU PublicLicense.
展开▼
