2026-07-23T19:24:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11000 2024-03-06T10:47:01Z ddc:004 open_access

On the Stretch Factor of Polygonal Chains Chen, Ke Dumitrescu, Adrian Mulzer, Wolfgang Tóth, Csaba D. polygonal chain vertex dilation Koch curve recursive construction 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, sum_{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 epsilon > 0, there is a noncrossing c-chain that has stretch factor Omega(n^{1/2-epsilon}), for sufficiently large constant c=c(epsilon); (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(n log n) space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ke Chen and Adrian Dumitrescu and Wolfgang Mulzer and Csaba D. Tóth 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.56 urn:nbn:de:0030-drops-110005 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.56 eng https://creativecommons.org/licenses/by/3.0/legalcode