Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, December 06, 2011, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Gabriel Nivasch (EPFL)
For every fixed d and every n, we construct an n-point set G in Rd such that every line in Rd is contained in a halfspace that contains only 2n/(d+2) points of G (up to lower-order terms).
Apparently, the point set G satisfies the following more general property: For every k, every k-flat in Rd is contained in a halfspace that contains only (k+1) n / (d+k+1) points of G (up to lower-order terms).
In 2008, Bukh, Matousek, and Nivasch conjectured the following generalization of Rado's centerpoint theorem: For every n-point set S in Rd and every k, there exists a k-flat f in Rd such that every halfspace that contains f contains at least (k+1) n / (d+k+1) points of S (up to lower-order terms). (The centerpoint theorem is obtained by setting k=0.) Such a flat f would be called a "centerflat".
Thus, our upper bound construction shows that the leading constant (k+1)/(k+d+1) in the above conjecture is tight (certainly for k = 1, and apparently for all k).
The set G of our construction is the "stretched grid" -- a point set which has been previously used by Bukh et al. for other related purposes.
Joint work with Boris Bukh.
Automatic MiSe System Software Version 1.4803M | admin login