Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 23, 2007, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Marek Sulovský
I will present one or two discrete geometric results dealing with curves in the plane. First of them is a recent upper bound O(n^(2-1/2s)) [Chan '05] on the complexity of k-levels in an arrangement of s-intersecting curve segments in the plane (where k-level is a closure of the set of all points lying on some of the curve segments, which have exactly k curve segments below them). Although the proof of this result is very simple, a better than quadratic bound has not been known for a long time.
If time permits, I will also talk about the upper bound on the complexity of k-level in an arrangement of lines, which is O(n^(4/3)) [Dey '98] and try to explain, how a theorem about singularities of curves can be used to prove this upper bound.
Automatic MiSe System Software Version 1.4803M | admin login