{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:45:09Z","timestamp":1787323509576,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["STG 757609"],"award-info":[{"award-number":["STG 757609"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1422311"],"award-info":[{"award-number":["CCF-1422311"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1423615"],"award-info":[{"award-number":["CCF-1423615"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1800734"],"award-info":[{"award-number":["DMS-1800734"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>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&lt;j&lt;k \\leq 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 $\\varepsilon &gt; 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&gt;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&gt;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.<\/jats:p>","DOI":"10.1137\/20m1335698","type":"journal-article","created":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T11:58:00Z","timestamp":1626695880000},"page":"1592-1614","source":"Crossref","is-referenced-by-count":0,"title":["On the Stretch Factor of Polygonal Chains"],"prefix":"10.1137","volume":"35","author":[{"given":"Ke","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adrian","family":"Dumitrescu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1948-5840","authenticated-orcid":true,"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,7,19]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1268550"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-007-9019-9"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/120890855"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00233-X"},{"key":"atypb5","first-page":"260","author":"Alamdari S.","year":"2012","journal-title":"New York"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/090780304"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1168-8"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2019.101595"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2013.04.002"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"P. Brass, W. O. J. Moser, and J. Pach,\n                      Research Problems in Discrete Geometry\n                      , Springer, New York, 2005,https:\/\/doi.org\/10.1007\/0-387-29929-7.","DOI":"10.1007\/0-387-29929-7"},{"key":"atypb11","unstructured":"E. Ces\u00e0ro,\n                      Remarques sur la courbe de von Koch\n                      , Atti R. Accad. Scienze Fis. Mat. Napoli, 12 (1905), reprinted as section 228 in Opere scelte, a cura dell'Unione matematica italiana e col contributo del Consiglio nazionale delle ricerche, Vol. 2: Geometria, analisi, fisica matematica, Edizioni Cremonese, Rome, 1964, pp. 464-479."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009478"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.12.001"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/BF00149359"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"H. T. Croft, K. J. Falconer, and R. K. Guy,\n                      Unsolved Problems in Geometry\n                      , Probl. Books in Math. 2, Springer, New York, 1991,https:\/\/doi.org\/10.1007\/978-1-4612-0963-8.","DOI":"10.1007\/978-1-4612-0963-8"},{"key":"atypb16","first-page":"168","author":"Das G.","year":"1989","journal-title":"New York"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2017.06.007"},{"key":"atypb18","first-page":"425","author":"Eppstein D.","year":"2000","journal-title":"Amsterdam"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00055-4"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01181430"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300000784"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/0116001"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004198003016"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/0402010"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.03.004"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100047022"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek,\n                      Lectures on Discrete Geometry\n                      , Grad. Texts in Math. 212, Springer, New York, 2002,https:\/\/doi.org\/10.1007\/978-1-4613-0039-7.","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-015-9701-2"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/0212052"},{"key":"atypb30","first-page":"849","author":"Mitchell J. S. B.","year":"2017","journal-title":"Boca Raton, FL"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361671"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"G. Narasimhan and M. H. M. Smid,\n                      Geometric Spanner Networks\n                      , Cambridge University Press, Cambridge, UK, 2007,https:\/\/doi.org\/10.1017\/CBO9780511546884.","DOI":"10.1017\/CBO9780511546884"},{"key":"atypb33","first-page":"47","volume":"7","author":"N\u00f6llenburg M.","year":"2016","journal-title":"J. Comput. Geom."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100071875"},{"key":"atypb35","first-page":"969","author":"Salowe J. S.","year":"2004","journal-title":"Boca Raton, FL"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1951-0045403-1"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1335698","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:06:32Z","timestamp":1787321192000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1335698"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1335698"],"URL":"https:\/\/doi.org\/10.1137\/20m1335698","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}