On the Stretch Factor of Polygonal Chains
share
Let P=(p_1, p_2, ..., p_n) be a polygonal chain. The stretch factor of P is the ratio between the total length of P and the distance of its endpoints, ∑_i = 1^n-1 |p_i p_i+1|/|p_1 p_n|. For a parameter c ≥ 1, we call P a c-chain if |p_ip_j|+|p_jp_k| ≤ c|p_ip_k|, for every triple (i,j,k), 1 ≤ i<j<k ≤ n. The stretch factor is a global property: it measures how close P is to a straight line, and it involves all the vertices of P; being a c-chain, on the other hand, is a fingerprint-property: it only depends on subsets of O(1) vertices of the chain. We investigate how the c-chain property influences the stretch factor in the plane: (i) we show that for every ε > 0, there is a noncrossing c-chain that has stretch factor Ω(n^1/2-ε), for sufficiently large constant c=c(ε); (ii) on the other hand, the stretch factor of a c-chain P is O(n^1/2), for every constant c≥ 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 R^2 with n vertices, the minimum c≥ 1 for which P is a c-chain in O(n^2.5 polylog n) expected time and O(nlog n) space.
READ FULL TEXT