A fast algorithm for approximating the detour of a polygonal chain. (Q1428113)

Given a non closed Jordan curve \(C\) in the plane, such that the length \(C_p^q\) of the curve between any two points \(p,q\in C\) is properly defined, the ratio between \(C_p^q\) and the Euclidean distance between \(p\) and \(q\) is called the \textsl{detour} of the curve on the portion between \(p\) and \(q\). The detour \(d_C\) of the whole curve is defined as the maximum detour between all pairs of points on \(C\). Computing exactly the detour of a curve \(C\) happens to be a very difficult problem in general, even for curves conceptually as simple as polygonal chains of \(n\) segments. For the latter case, the authors provide in this paper an algorithm that approximates the detour in the following sense: for any given value of \(\epsilon>0\) their algorithm allows to find in \(O({1\over{\epsilon}} n\log n)\) running time a pair of points \(p,q\in C\) such that \(d_C\leq (1+\epsilon)C_p^q\).