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 .

Web Address: www.cs.mcgill.ca/~beezer/Seminars/seminar99.html