Long monotone paths in line arrangements

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

Research output: Contribution to journalArticle

Abstract

We show how to construct an arrangement of n lines having a monotone path of length Ω(n2-(d/√logn), where d > 0 is some constant, and thus nearly settle the long standing question on monotone path length in line arrangements.

Original languageEnglish (US)
Pages (from-to)167-176
Number of pages10
JournalDiscrete and Computational Geometry
Volume32
Issue number2
DOIs
StatePublished - Sep 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

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

  • Cite this