Long monotone paths in line arrangements

József Balogh, Oded Regev, Clifford Smyth, William Steiger, Mario Szegedy

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The method to construct an arrangement of n lines having a monotone path was presented. It was observed that k parallel horizontal lines and k parallel vertical lines uses n lines and has a length n=2k. It was found that a path is monotone in direction (a,b) if its sequence of vertices is monotone when projected orthogonally along the line with equation ay-bx=0.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual Symposium on Computational Geometry
Pages124-128
Number of pages5
StatePublished - 2003
EventNineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States
Duration: Jun 8 2003Jun 10 2003

Other

OtherNineteenth Annual Symposium on Computational Geometry
CountryUnited States
Citysan Diego, CA
Period6/8/036/10/03

Keywords

  • Discrete Line Arrangements
  • Monotone Paths

ASJC Scopus subject areas

  • Software
  • Geometry and Topology
  • Safety, Risk, Reliability and Quality
  • Chemical Health and Safety

Fingerprint Dive into the research topics of 'Long monotone paths in line arrangements'. Together they form a unique fingerprint.

  • Cite this

    Balogh, J., Regev, O., Smyth, C., Steiger, W., & Szegedy, M. (2003). Long monotone paths in line arrangements. In Proceedings of the Annual Symposium on Computational Geometry (pp. 124-128)