Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, June 04, 2009, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Gabriel Nivasch (Tel Aviv Univ., Israel)
Given a point set X in R^d and a parameter epsilon<1, a "weak epsilon-net" for X is another point set N that intersects every convex set in R^d that contains an epsilon fraction of the points of X. The problem is to build such an N of minimal size. We show that, for cases in which the given set X lies in a so-called "convex curve" (a curve that is intersected at most d times by every hyperplane), there are upper and lower bounds for the size of N which are only slightly superlinear in 1/epsilon. The bounds have a complicated form involving the extremely slow-growing inverse Ackermann function. We obtain these results by reduction to a new combinatorial problem, interesting on its own right, which we call "stabbing interval chains". Amazingly, so-called Davenport-Schinzel sequences (an unrelated problem) are known to have almost-identical bounds. Inspired by our results on interval chains, we also improve the upper bounds for DS sequences.
Joint work with Noga Alon, Boris Bukh, Haim Kaplan, Jiří Matoušek, Micha Sharir, and Shakhar Smorodinsky.
Automatic MiSe System Software Version 1.4803M | admin login