On the Stretch Factor of Polygonal Chains

Let $P=(p_1, p_2, \dots, p_n)$ be a polygonal chain in $\mathbb{R}^d$. The stretch factor of $P$ is the ratio between the total length of $P$ and the distance of its endpoints, $\sum_{i = 1}^{n-1} |p_i p_{i+1}|/|p_1 p_n|$. For a parameter $c \geq 1$, we call $P$ a $c$-chain if $|p_ip_j|+|p_jp_k| \leq c|p_ip_k|$ for every triple $(i,j,k)$, $1 \leq i 0$, there is a noncrossing $c$-chain that has stretch factor $\Omega(n^{1/2-\varepsilon})$ for sufficiently large constant $c=c(\varepsilon)$; (ii) on the other hand, the stretch factor of a $c$-chain $P$ is $O(n^{1/2})$ for every constant $c\geq 1$, regardless of whether $P$ is crossing or noncrossing; and (iii) we give a randomized algorithm that can determine, for a polygonal chain $P$ in $\mathbb{R}^2$ with $n$ vertices, the minimum $c\geq 1$ for which $P$ is a $c$-chain in $O(n^{2.5}\ {\rm polylog}\ n)$ expected time and $O(n\log n)$ space. These results generalize to $\mathbb{R}^d$. For every dimension $d\geq 2$ and every $\varepsilon>0$, we construct a noncrossing $c$-chain that has stretch factor $\Omega(n^{(1-\varepsilon)(d-1)/d})$; on the other hand, the stretch factor of any $c$-chain is $O((n-1)^{(d-1)/d})$; for every $c>1$, we can test whether an $n$-vertex chain in $\mathbb{R}^d$ is a $c$-chain in $O(n^{3-1/d}\ {\rm polylog}\ n)$ expected time and $O(n\log n)$ space.