A 'taut string algorithm' for straightening a piecewise linear path in two dimensions

摘要

A piecewise linear path in two dimensions is formed by drawing straight lines between adjacent points in the sequence {u_i:i = 1, 2,…, n}. Let Δ be a given positive number such that the length of each straight line segment is at least 3Δ. We straighten the path in the following way. For i = 2, 3,…, n-1, we surround u_i by a circular ring of radius Δ and centre u_i. Then a piece of string that begins at u_l and ends at u_n is threaded through all the rings in sequence. The new path is constructed by pulling the string tight. An iterative algorithm is proposed that generates the new path to prescribed accuracy. Its convergence is proved and its efficiency is demonstrated by some numerical results.