 License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.56
URN: urn:nbn:de:0030-drops-110005
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11000/
 Go to the corresponding LIPIcs Volume Portal

### On the Stretch Factor of Polygonal Chains

 pdf-format:

### Abstract

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.

### BibTeX - Entry

```@InProceedings{chen_et_al:LIPIcs:2019:11000,
author =	{Ke Chen and Adrian Dumitrescu and Wolfgang Mulzer and Csaba D. T{\'o}th},
title =	{{On the Stretch Factor of Polygonal Chains}},
booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages =	{56:1--56:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-117-7},
ISSN =	{1868-8969},
year =	{2019},
volume =	{138},
editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 