**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 GraphSearch.

Publication# Hitting Simplices with Points in $R^3$

Abstract

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).

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Loading

Related publications

Loading

Related publications

No results

Related concepts (7)

Three-dimensional space

In geometry, a three-dimensional space (3D space, 3-space or, rarely, tri-dimensional space) is a mathematical space in which three values (coordinates) are required to determine the position of a p

Simplex

In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simpl

Open problem

In science and mathematics, an open problem or an open question is a known problem which can be accurately stated, and which is assumed to have an objective and verifiable solution, but which has not