Paths with no Small Angles | SpringerLink
Skip to main content
Springer Nature Link
Log in

Paths with no Small Angles

  • Conference paper
LATIN 2008: Theoretical Informatics (LATIN 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4957))

Included in the following conference series:

Abstract

Giving a partial solution to a problem of S. Fekete and G.J. Woeginger [3,4] we show that given a finite set X of points in the plane, it is possible to arrange them on a polygonal path (with the vertex set X) so that every angle on the polygonal path is at least π/9. According to a conjecture of Fekete and Woeginger, π/9 can be replaced by π/6. Previously, the result has not been known with any positive constant.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Aichholzer, O., Hackl, T., Hoffmann, M., Huemer, C., Pór, A., Santos, F., Speckmann, B., Vogtenhuber, B.: Maximizing Maximal Angles for Plane Straight-Line Graphs. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol. 4619, pp. 458–469. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  2. Bárány, I., Pór, A., Valtr, P.: Paths with no small angles (manuscript in preparation, 2007)

    Google Scholar 

  3. Fekete, S.: Geometry and the Travelling Salesman Problem, Ph.D. thesis, University of Waterloo (1992)

    Google Scholar 

  4. Fekete, S., Woeginger, G.J.: Angle-restricted tours in the plane. Comput. Geom.: Theory and Appl. 8, 195–218 (1997)

    MathSciNet  Google Scholar 

  5. Kirkpatrick, Seidel, R.: The ultimate planar convex hull algorithm. SIAM J. Computing 15, 286–297 (1986)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Rényi Institute of Mathematics, Hungarian Academy of Sciences, POBox 127, 1364, Budapest, Hungary

    Imre Bárány

  2. Department of Mathematics, University College London, Gower Street, London, WC1E 6BT, England

    Imre Bárány

  3. Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00, Praha 1, Czech Republic

    Attila Pór & Pavel Valtr

Authors
  1. Imre Bárány
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Attila Pór
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pavel Valtr
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Eduardo Sany Laber Claudson Bornstein Loana Tito Nogueira Luerbio Faria

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bárány, I., Pór, A., Valtr, P. (2008). Paths with no Small Angles. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds) LATIN 2008: Theoretical Informatics. LATIN 2008. Lecture Notes in Computer Science, vol 4957. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78773-0_56

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-78773-0_56

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-78772-3

  • Online ISBN: 978-3-540-78773-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation