Long Monotone Paths in Line Arrangements |
| |
| Authors: | Jó zsef Balogh, Oded Regev, Clifford Smyth, William Steiger Mario Szegedy |
| |
| Affiliation: | (1) Department of Mathematics, The Ohio State University, Columbus, OH 43210, USA;(2) EECS Department, University of California at Berkeley, Berkeley, CA 94720, USA;(3) Department of Mathematical Sciences, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15213, USA;(4) Department of Computer Science, Rutgers University, 110 Frelinghuysen Rd., Piscataway, NJ 08854, USA |
| |
| Abstract: | We show how to construct an arrangement of n lines having a monotone path oflength (n2 – (d/sqrt{log n})), where d > 0 is some constant, and thusnearly settle the long standing question on monotone path length in linearrangements. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
