| [home] - [up] |
Colloquium - 16:00
Abstract: In this talk, we give subquadratic bounds on the maximum length of an x-monotone path in an arrangement of n lines with at most C log log n directions, where C is a suitable constant. For instance, the maximum length of an x-monotone path in an arrangement of n lines having at most 10 slopes is O(n^{67/34}). In particular, we get tight estimates for the case of lines having at most five directions, by showing that previous constructions -- Omega(n^{3/2}) for arrangements with four slopes and Omega(n^{5/3}) for arrangements with five slopes -- due to Sharir and Matousek respectively, are (asymptotically) best possible.