McGill University - School of Computer Science

# Algorithms Seminar 2002

Everybody is welcome!

 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}).

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at beezer(at)cs.mcgill.ca. , or sl@jeff.cs.mcgill.ca .