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


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
Number of pages5
StatePublished - 2003
EventNineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States
Duration: Jun 8 2003Jun 10 2003


OtherNineteenth Annual Symposium on Computational Geometry
Country/TerritoryUnited States
Citysan Diego, CA


  • Discrete Line Arrangements
  • Monotone Paths

ASJC Scopus subject areas

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


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

Cite this