Document Open Access Logo

On the Stretch Factor of Polygonal Chains

Authors Ke Chen , Adrian Dumitrescu , Wolfgang Mulzer , Csaba D. Tóth

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.56.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Ke Chen
  • Department of Computer Science, University of Wisconsin - Milwaukee, USA
Adrian Dumitrescu
  • Department of Computer Science, University of Wisconsin - Milwaukee, USA
Wolfgang Mulzer
  • Institut für Informatik, Freie Universität Berlin, Germany
Csaba D. Tóth
  • Department of Mathematics, California State University Northridge, Los Angeles, CA
  • Department of Computer Science, Tufts University, Medford, MA, USA

Funding

  • Mulzer, Wolfgang: Partially supported by ERC STG 757609.
  • Tóth, Csaba D.: Supported in part by NSF CCF-1422311 and CCF-1423615.

Acknowledgements

This work was initiated at the Fields Workshop on Discrete and Computational Geometry, held July 31 - August 4, 2017, at Carleton University. The authors thank the organizers and all participants of the workshop for inspiring discussions and for providing a great research atmosphere. This problem was initially posed by Rolf Klein in 2005. We would like to thank Rolf Klein and Christian Knauer for interesting discussions on the stretch factor and related topics.

Cite As Get BibTex

Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer, and Csaba D. Tóth. On the Stretch Factor of Polygonal Chains. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.56

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Paths and connectivity problems
  • Theory of computation → Computational geometry
Keywords
  • polygonal chain
  • vertex dilation
  • Koch curve
  • recursive construction

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Pankaj K. Agarwal, Rolf Klein, Christian Knauer, Stefan Langerman, Pat Morin, Micha Sharir, and Michael A. Soss. Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles in 2D and 3D. Discrete & Computational Geometry, 39(1-3):17-37, 2008. URL: https://doi.org/10.1007/s00454-007-9019-9.
  2. Pankaj K. Agarwal, Jiří Matoušek, and Micha Sharir. On Range Searching with Semialgebraic Sets. II. SIAM J. Computing, 42(6):2039-2062, 2013. URL: https://doi.org/10.1137/120890855.
  3. Oswin Aichholzer, Franz Aurenhammer, Christian Icking, Rolf Klein, Elmar Langetepe, and Günter Rote. Generalized self-approaching curves. Discrete Applied Mathematics, 109(1-2):3-24, 2001. URL: https://doi.org/10.1016/S0166-218X(00)00233-X.
  4. Soroush Alamdari, Timothy M. Chan, Elyot Grant, Anna Lubiw, and Vinayak Pathak. Self-approaching Graphs. In Walter Didimo and Maurizio Patrignani, editors, Proc. 20th Symposium on Graph Drawing (GD), volume 7704 of LNCS, pages 260-271, Berlin, 2012. Springer. URL: https://doi.org/10.1007/978-3-642-36763-2_23.
  5. Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, and Santosh Vempala. Local Versus Global Properties of Metric Spaces. SIAM J. Computing, 41(1):250-271, 2012. URL: https://doi.org/10.1137/090780304.
  6. Prosenjit Bose, Joachim Gudmundsson, and Michiel H. M. Smid. Constructing Plane Spanners of Bounded Degree and Low Weight. Algorithmica, 42(3-4):249-264, 2005. URL: https://doi.org/10.1007/s00453-005-1168-8.
  7. Prosenjit Bose, Irina Kostitsyna, and Stefan Langerman. Self-Approaching Paths in Simple Polygons. In Boris Aronov and Matthew J. Katz, editors, Proc. 33rd Symposium on Computational Geometry (SoCG), volume 77 of LIPIcs, pages 21:1-21:15. Schloss Dagstuhl, 2017. URL: https://doi.org/10.4230/LIPIcs.SoCG.2017.21.
  8. Prosenjit Bose and Michiel H. M. Smid. On plane geometric spanners: A survey and open problems. Computational Geometry: Theory and Applications, 46(7):818-830, 2013. URL: https://doi.org/10.1016/j.comgeo.2013.04.002.
  9. Peter Brass, William O. J. Moser, and János Pach. Research Problems in Discrete Geometry. Springer, New York, 2005. Google Scholar
  10. Ernesto Cesàro. Remarques sur la courbe de von Koch. Atti della R. Accad. della Scienze fisiche e matem. Napoli, 12(15), 1905. Reprinted as \S228 in Opere scelte, a cura dell'Unione matematica italiana e col contributo del Consiglio nazionale delle ricerche, Vol. 2: Geometria, analisi, fisica matematica, Rome, dizioni Cremonese, pp. 464-479, 1964. Google Scholar
  11. Timothy M. Chan. Geometric Applications of a Randomized Optimization Technique. Discrete & Computational Geometry, 22(4):547-567, 1999. URL: https://doi.org/10.1007/PL00009478.
  12. Otfried Cheong, Herman J. Haverkort, and Mira Lee. Computing a minimum-dilation spanning tree is NP-hard. Computational Geometry: Theory and Applications, 41(3):188-205, 2008. URL: https://doi.org/10.1016/j.comgeo.2007.12.001.
  13. Fan R. K. Chung and Ron L. Graham. On Steiner trees for bounded point sets. Geometriae Dedicata, 11(3):353-361, 1981. URL: https://doi.org/10.1007/BF00149359.
  14. Hallard T. Croft, Kenneth J. Falconer, and Richard K. Guy. Unsolved Problems in Geometry, volume 2 of Unsolved Problems in Intuitive Mathematics. Springer, New York, 1991. URL: https://doi.org/10.1007/978-1-4612-0963-8.
  15. Gautam Das and Deborah Joseph. Which Triangulations Approximate the Complete Graph? In Hristo Djidjev, editor, Proc. International Symposium on Optimal Algorithms, volume 401 of LNCS, pages 168-192, Berlin, 1989. Springer. URL: https://doi.org/10.1007/3-540-51859-2_15.
  16. Adrian Dumitrescu and Minghui Jiang. Minimum rectilinear Steiner tree of n points in the unit square. Computational Geometry: Theory and Applications, 68:253-261, 2018. URL: https://doi.org/10.1016/j.comgeo.2017.06.007.
  17. David Eppstein. Spanning trees and spanners. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, chapter 9, pages 425-461. Elsevier, Amsterdam, 2000. Google Scholar
  18. David Eppstein. Beta-skeletons have unbounded dilation. Computational Geometry: Theory and Applications, 23(1):43-52, 2002. URL: https://doi.org/10.1016/S0925-7721(01)00055-4.
  19. László Fejes Tóth. Über einen geometrischen Satz. Mathematische Zeitschrift, 46:83-85, 1940. Google Scholar
  20. Leonard Few. The shortest path and the shortest road through n points. Mathematika, 2(2):141-144, 1955. URL: https://doi.org/10.1112/S0025579300000784.
  21. Edgar N. Gilbert and Henry O. Pollak. Steiner minimal trees. SIAM Journal on Applied Mathematics, 16(1):1-29, 1968. URL: https://doi.org/10.1137/0116001.
  22. Christian Icking, Rolf Klein, and Elmar Langetepe. Self-approaching curves. Mathematical Proceedings of the Cambridge Philosophical Society, 125(3):441-453, 1999. Google Scholar
  23. Howard J. Karloff. How Long can a Euclidean Traveling Salesman Tour Be? SIAM Journal on Discrete Mathematics, 2(1):91-99, 1989. URL: https://doi.org/10.1137/0402010.
  24. Rolf Klein, Christian Knauer, Giri Narasimhan, and Michiel H. M. Smid. On the dilation spectrum of paths, cycles, and trees. Computational Geometry: Theory and Applications, 42(9):923-933, 2009. URL: https://doi.org/10.1016/j.comgeo.2009.03.004.
  25. David G. Larman and Peter McMullen. Arcs with increasing chords. Mathematical Proceedings of the Cambridge Philosophical Society, 72(2):205-207, 1972. URL: https://doi.org/10.1017/S0305004100047022.
  26. Jiří Matoušek. Lectures on Discrete Geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002. URL: https://doi.org/10.1007/978-1-4613-0039-7.
  27. Jiří Matoušek and Zuzana Patáková. Multilevel Polynomial Partitions and Simplified Range Searching. Discrete & Computational Geometry, 54(1):22-41, 2015. URL: https://doi.org/10.1007/s00454-015-9701-2.
  28. Nimrod Megiddo. Linear-Time Algorithms for Linear Programming in ℝ³ and Related Problems. SIAM J. Computing, 12(4):759-776, 1983. URL: https://doi.org/10.1137/0212052.
  29. Joseph S. B. Mitchell and Wolfgang Mulzer. Proximity algorithms. In Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth, editors, Handbook of Discrete and Computational Geometry, chapter 32, pages 849-874. CRC Press, Boca Raton, 3rd edition, 2017. URL: https://doi.org/10.1201/9781315119601.
  30. Giri Narasimhan and Michiel H. M. Smid. Approximating the Stretch Factor of Euclidean Graphs. SIAM J. Comput., 30(3):978-989, 2000. URL: https://doi.org/10.1137/S0097539799361671.
  31. Giri Narasimhan and Michiel H. M. Smid. Geometric Spanner Networks. Cambridge University Press, 2007. URL: https://doi.org/10.1017/CBO9780511546884.
  32. Martin Nöllenburg, Roman Prutkin, and Ignaz Rutter. On self-approaching and increasing-chord drawings of 3-connected planar graphs. Journal of Computational Geometry, 7(1):47-69, 2016. URL: http://jocg.org/index.php/jocg/article/view/223, URL: https://doi.org/10.20382/jocg.v7i1a3.
  33. Günter Rote. Curves with increasing chords. Mathematical Proceedings of the Cambridge Philosophical Society, 115(1):1-12, 1994. URL: https://doi.org/10.1017/S0305004100071875.
  34. Jeffrey S. Salowe. Parametric search. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 43, pages 969-982. CRC Press, Boca Raton, 2nd edition, 2004. URL: https://doi.org/10.1201/9781420035315.
  35. Samuel Verblunsky. On the shortest path through a number of points. Proceedings of the American Mathematical Society, 2:904-913, 1951. URL: https://doi.org/10.1090/S0002-9939-1951-0045403-1.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact