Long monotone paths in line arrangements
Jazsef Balogh, Oded Regev, Clifford Smyth, William Steiger, Márió Szegedy · 2003
We show how to construct an arrangement of n lines having a monotone path of length O(n2-(d/vlog n)), where d>0 is some constant, and thus nearly settle the long standing question on monotone path length in line arrangements.