Stabbing simplices by points and flats

Abstract: The following result was proved by Barany in 1982: For every d >= 1 there exists c_d > 0 such that for every n-point set S in R^d there is a point p in R^d contained in at least c_d n^{d+1} - O(n^d) of the simplices spanned by S. We investigate the largest possible value of c_d. It was known that c_d <= 1/(2^d(d+1)!) (this estimate actually holds for every point set S). We construct sets showing that c_d <= (d+1)^{-(d+1)}, and we conjecture this estimate to be tight. The best known lower bound, due to Wagner, is c_d >= gamma_d := (d^2+1)/((d+1)!(d+1)^{d+1}); in his method, p can be chosen as any centerpoint of S. We construct n-point sets with a centerpoint that is contained in no more than gamma_d n^{d+1}+O(n^d) simplices spanned by S, thus showing that the approach using an arbitrary centerpoint cannot be further improved. We also prove that for every n-point set S in R^d there exists a (d-2)-flat that stabs at least c_{d,d-2} n^3 - O(n^2) of the triangles spanned by S, with c_{d,d-2}>=(1/24)(1- 1/(2d-1)^2). To this end, we establish an equipartition result of independent interest (generalizing planar results of Buck and Buck and of Ceder): Every mass distribution in R^d can be divided into 4d-2 equal parts by 2d-1 hyperplanes intersecting in a common (d-2)-flat.

Review text

The following result was proved by \textit{I. Bárány} [Discrete Math. 40, 141--152 (1982; Zbl 0492.52005)]: For every \(d \geq 1\) there exists \(c_d > 0\) such that for every \(n\)-point set~\(S\) in~\({\mathbb R}^d\) there is a~point \(p \in {\mathbb R}^d\) contained in at least \(c_dn^{d+1} -O(n^d)\) of the \(d\)-dimensional simplices spanned by~\(S\). The authors of the present paper examine the largest possible value of~\(c_d\), construct sets showing that \(c_d \leq (d + 1)^{-(d+1)}\), and conjecture that this estimate is tight; in this method \(p\) is~chosen as any centerpoint of~\(S\). It is also proved that, for every \(n\)-point set \(S\subset {\mathbb R}^d\), there exists a~\((d-2)\)-flat that stabs at least \(c_{d,d-2} n ^3-O(n^2)\) of the triangles spanned by~\(S\), with \(c_{d,d-2}\geq \frac 1{24} (1-1/ (2d-1)^2)\). This is established with the help of an~equipartition result of independent interest (generalizing planar results of \textit{R.~C.~Buck} and \textit{E.~F.~Buck} [Math. Mag. 22, 195--198 (1948/49)] and and of \textit{J.~Ceder} [Bol. Soc. Mat. Mexicana (2) 9, 28--32 (1964; Zbl 0158.19802)]: Every mass distribution in~\({\mathbb R}^d\) can be divided into \(4d - 2\) equal parts by \(2d - 1\) hyperplanes intersecting in a~common \((d - 2)\)-flat.

Recommendations

Cites work

Cited in

(32)

This page was built for publication: Stabbing simplices by points and flats

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q848667)