Long monotone paths in line arrangements

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

Research output: Contribution to conferencePaperpeer-review


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)
Number of pages5
StatePublished - Jul 28 2003
Externally publishedYes
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

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


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

Cite this