Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Publication
Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
The so-called first selection lemma states the following: given any set P of n points in a"e (d) , there exists a point in a"e (d) contained in at least c (d) n (d+1)-O(n (d) ) simplices spanned by P, where the constant c (d) depends on d. We present improved bounds on the first selection lemma in a"e(3). In particular, we prove that c (3)a parts per thousand yen0.00227, improving the previous best result of c (3)a parts per thousand yen0.00162 by Wagner (On k-sets and applications. Ph.D. thesis, ETH Zurich, 2003). This makes progress, for the three-dimensional case, on the open problems of Bukh et al. (Stabbing simplices by points and flats. Discrete Comput. Geom., 2010) (where it is proven that c (3)a parts per thousand currency sign1/4(4)a parts per thousand 0.00390) and Boros and Furedi (The number of triangles covering the center of an n-set. Geom. Dedic. 17(1):69-77, 1984) (where the two-dimensional case was settled).