Long monotone paths in line arrangements

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

Research output: Contribution to conferencePaper

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)
Pages124-128
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

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

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

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. 124-128. Paper presented at Nineteenth Annual Symposium on Computational Geometry, san Diego, CA, United States.