| DATE: | Monday December 2nd, 2002 |
| TIME: | 10:00 AM - 11:00 AM |
| PLACE: | McConnell 320 |
| TITLE: | Monotone Paths in Line Arrangements |
| SPEAKER: | William Steiger from Rutgers University, NJ |
Let L={l_1,\ldots,l_n} be a set of n given lines in R^2. A path in the arrangement is a simple polygonal chain joining a set of distinct vertices in V={l_i cap l_j, i < j} by segments which are on lines in L. The length of a path is one plus the number of vertices in V at which the path turns. A path is monotone along a line ax+by=c if its sequence of vertices is monotone when projected orthogonally onto the line. An interesting open question asks for the value of lambda_n, the maximal monotone path length that can occur in an arrangement of n lines. Clearly, lambda_n <= {n\choose 2}.
I will explain the construction of an arrangement of n lines
in which there is a monotone path of length
Omega(n^2/C^{sqrt logn}), C > 1 a suitable constant. This
improves an earlier bound of Omega(n^{7/4}).