1 Introduction

The results of this paper were motivated by the following problem by Imre Bárány.

Problem

For any two points \(x,y \in \mathbb {R}^n\), let S(x, y) be the Euclidean ball with diameter [x, y]. Find the optimal constant \(b_n\), if it exists, depending only on the dimension such that for any set \(X \subset \mathbb {R}^n\) with \(|X|= N\), there a point z contained in at least \(b_n N^2\) sets of the form S(x, y) with \(x, y \in X\).

This is representative of a wide class of problems in discrete geometry which we call positive-fraction problems. A positive-fraction problem is a problem that has the following setting. Suppose we are given a family \({\mathcal {A}}\) of sets in \(\mathbb {R}^n\), and assume that the family \({\mathcal {A}}\) has some prescribed property (e.g., all members of \({\mathcal {A}}\) are convex, or \({\mathcal {A}}\) is the family of all n-simplices on given vertices, etc.). Determine if there exists \(\alpha > 0\) depending only on the dimension n and on the property of \({\mathcal {A}}\), but not on \(|{\mathcal {A}}|\), such that there is a subfamily \({\mathcal {B}} \subset {\mathcal {A}}\) with non-empty intersection and \(|{\mathcal {B}}| \ge \alpha |{\mathcal {A}}|\).

There are several well-known positive-fraction problems that have an affirmative answer (a positive-fraction result). Classic examples include the fractional Helly theorem by Katchalski and Liu [16] and the first selection lemma by Bárány [2, Thm. 5.1] (as called in [19]).

The first selection lemma states that for any finite set X of points in \(\mathbb {R}^n\), there is a point z contained in a positive fraction \(c_n\) of the simplices spanned by X, where \(c_n\) depends on the dimension.

In 1984 Boros and Füredi [7] proved that \(c_2 \ge \frac{2}{9}\). Different proofs of this result have been discovered recently [8, 12]. The cases \(n=1,2\) are the only where the optimal constant is known [9]. The first high-dimensional version was proved by Bárány [2]. Namely,

Theorem

(First selection lemma) Let \(S \subset \mathbb {R}^n,\) with \(|S|=N\). There is a constant \(c_n\) depending only on the dimension such that we can always find an intersecting family \(\mathcal {F}\) of simplices with vertices in S such that

$$\begin{aligned} |\mathcal {F}| \ge c_n \left( {\begin{array}{c}N\\ n+1\end{array}}\right) \end{aligned}$$

There have been several improvements on the result above; either finding better bounds on the constant \(c_n\) [13, 17, 21], or requiring more conditions that the intersecting simplices have to satisfy, as in [14, 15, 22, 24].

While an n-dimensional simplex is a natural hull of \(n + 1\) points, there are several ways to define a hull of two points in \(\mathbb {R}^n\). One is, as in Bárány’s problem, to consider Euclidean ball with the diameter [x, y] as a hull of two points \(x, y \in \mathbb {R}^n\). For this setup we prove a bound \(b_n \ge \frac{1}{n + 1}\) in Theorem 2.1.

One can notice that the first selection lemma itself gives a positive answer for Bárány’s problem. Indeed, take z to be a point that is contained in a positive fraction of simplices with vertices in X. One can show that for each simplex \({{\mathrm{conv}}}\{ x_1, x_2, \ldots , x_{n + 1} \} \ni z\) one has \(z \in S(x_i, x_j)\) for at least \(\frac{n + 1}{2}\) pairs (i, j). If we record all such pairs of points from all simplices containing z, then a pair of points cannot be mentioned more than \(\left( {\begin{array}{c}|X|\\ n - 1\end{array}}\right) \) times, so sufficiently many distinct pairs are mentioned. The arguments needed to show that z is covered many times are similar to the ones used in [4].

However, the estimate for \(b_n\) obtained by the double counting method above is only about 1 / (n!). At the moment the authors are not aware of any shape S(x, y) for which the double counting method with the first selection lemma gives the best constants. Therefore we leave its details to the interested reader.

It is interesting to consider “thinner” shapes as the hull of two points (i.e. the shapes that are more stretched along the segment [x, y] than a ball). For this purpose we introduce the following definition of a t-shape (with \(t \in (0, 1)\)).

Definition 1.1

Let \(t > 0\). A mapping S from \(\mathbb {R}^n \times \mathbb {R}^n\) to the set of measurable subsets of \(\mathbb {R}^n\) will be called a t-shape if for all \(x\ne y\) one has \(S(x,y) = S(y,x)\) and for all r that satisfy \(|x-y|\ge r>0\) one has

$$\begin{aligned} {{\mathrm{Vol}}}(S(x,y)\cap B_r(y))\ge t\cdot {{\mathrm{Vol}}}(B_r(y)), \end{aligned}$$

where \({{\mathrm{Vol}}}({\cdot })\) stands for the Euclidean volume, \(B_r(x)\) is the closed ball of radius r around x, \(|x-y|\) is the Euclidean distance between x and y.

This definition is very relaxed, the following more familiar shapes are examples of t-shapes for some t.

Example 1

For every \(a>0\), the ellipsoids

$$\begin{aligned} E_a(x,y) = \{z \in \mathbb {R}^n : |z-x| + |z-y| \le (1+a) |x-y| \} \end{aligned}$$

are t-shapes for some \(t=t_1(n,a)\).

Example 2

For every \(\pi >a>0\), the shapes

$$\begin{aligned} S_a(x,y) = \{z \in \mathbb {R}^n : \angle (x-z,y-z) \ge a \} \end{aligned}$$

are t-shapes for some \(t=t_2(n,a)\). In particular, if \(a = \pi / 2\), then \(S_a(x,y)\) is simply the Euclidean ball with diameter [x, y]. For a general a these sets are also called a-lenses, and families of these objects have nice intersection properties [3, 5].

We give a positive answer to Bárány’s problem where S(x, y) are no longer required to be balls, but are t-shapes for some \(t > 0\). In this case the fraction of intersecting hulls we can guarantee decreases exponentially in n for every fixed t.

Theorem 1.2

(Positive fraction intersection for t-shapes) There exist positive absolute constants \(c_1\) and \(c_2\) satisfying the following property. For every t-shape S(x, y) in \(\mathbb {R}^n,\) and for every finite X with \(|X| \ge N\) setting

$$\begin{aligned} \lambda = c_1 \cdot t \cdot c_2^n \end{aligned}$$

guarantees that there is a point \(z \in \mathbb {R}^n\) that is covered by at least \(\lambda N^2\) shapes S(x, y) with \(x,y \in X\).

In Theorem 4.1 we also consider the shape S(x, y) to be the minimal box (i.e. a parallelotope with edges parallel to coordinate lines) containing x and y. A box is not a t-shape for any \(t > 0\), but a positive-fraction result can also be proved. In this case the fraction also decreases exponentially in the dimension.

We should emphasise that a condition on the sets S(x, y) is necessary, as considering S(x, y) to be the segment [x, y] fails to give a positive-fraction result.

One of the most striking applications of the first selection lemma is the proof of existence of weak \(\varepsilon \)-nets for convex sets, presented below.

Theorem

(Alon et al. [1]) Let n be a positive integer,  and \(1 \ge \varepsilon > 0\). Then,  there is a positive integer \(m = m(n,\varepsilon )\) such that the following holds. For every finite set \(S \subset \mathbb {R}^n,\) there is a set \({\mathcal {T}} \subset \mathbb {R}^n\) of m points such that if \(A \subset S\) is a subset with size at least \(\varepsilon |S|,\) then

$$\begin{aligned} {\mathcal {T}} \cap {\text {conv}}(A) \ne \emptyset . \end{aligned}$$

Moreover,  \(m = O(\varepsilon ^{-n-1})\) where the implied constant of the O notation depends on n.

The set \({\mathcal {T}}\) is called a weak \(\varepsilon \)-net of S. Bounding the size of a weak \(\varepsilon \)-net for convex sets is a notorious problem. The best improvement over the bound above is \(m = O(\varepsilon ^{-n}\cdot {\text {polylog}}(\varepsilon ^{-1}))\) [11, 20]. The best lower bound is \(m = \Omega (\varepsilon ^{-1}\cdot \log ^{n-1} (\varepsilon ^{-1}))\) [10].

We explore variations of weak \(\varepsilon \)-nets for operators different from the convex hull. For instance, in Theorem 5.1 we show that the topological versions of the selection theorem imply directly a topological extension of weak \(\varepsilon \)-nets for convex sets, using the same arguments as [1]. This generalises weak \(\varepsilon \)-nets just like the topological Tverberg theorem generalises Tverberg’s theorem [6, 25]. We also consider variants of weak \(\varepsilon \)-nets for t-shapes. Given a t-shape S, we can define the thin hull of a set A as

$$\begin{aligned} {\text {thin}}_S(A) = \bigcup \{S(x,y) : x,y \in A\} \end{aligned}$$

Since t-shapes admit a first selection lemma, this operator begs for the existence of weak \(\varepsilon \)-nets.

Theorem 1.3

Let n be a positive integer,  \(\varepsilon , t >0,\) and S a t-shape in \(\mathbb {R}^n\). Then,  there is a positive integer \(m' = m'(t,\varepsilon , n)\) such that the following holds. For any finite set \(X \subset \mathbb {R}^n,\) there is a set \({\mathcal {T}} \subset \mathbb {R}^n\) of size \(m'\) such that if \(A \subset X\) and \(|A| \ge \varepsilon |X|,\) then

$$\begin{aligned} T \cap {\text {thin}}_S (A) \ne \emptyset . \end{aligned}$$

Moreover,  \(m' = O(\varepsilon ^{-2}),\) where the implied constant of the O notation depends on n and t.

The rest of the paper is organised as follows. In Sect. 2 we give a solution Bárány’s original problem. In Sect. 3 we prove our results on t-shapes. In Sect. 4 we state and prove our results for boxes. Finally, in Sect. 5 we prove all our results regarding weak \(\varepsilon \)-nets.

2 Positive-fraction result for Euclidean balls

In this section we give a solution to the original Bárány’s problem with a large constant. We prove a stronger version of the result, in the same spirit as Karasev’s colourful version of Bárány’s result [15]. Namely, instead of having one finite set X, we are given two sets A, B. We give a positive fraction intersection result for the balls having diameters with one end in A and another in B. The case \(A=B\) is Bárány’s problem.

Theorem 2.1

For each \(x,y \in \mathbb {R}^n\) let S(x, y) be the Euclidean ball with diameter [x, y]. Then,  for finite sets \(A, B \subset \mathbb {R}^n\) of N and M points respectively,  there is a point covered by at least \(\frac{1}{n + 1}NM\) sets of the form S(a, b) with \(a \in A,b \in B\).

Proof

By Rado’s central point theorem [23], there is a point \(z \in \mathbb R^n\) such that for every close half-space that contains z also contains at least \(\frac{N}{n + 1}\) points of the set A. Consider a point \(b \in B\). If \(b = z\), then the ball S(a, b) contains z for any \(a \in A\).

If \(b \ne z\), then consider a hyperplane through z orthogonal to the segment [b, z]. Let H be the closed half-space of this hyperplane that does not contain b. Then for any \(a \in A \cap H\) the angle \(\angle bza\) is not acute, and therefore \(z \in S(a, b)\). Hence every point \(b \in B\) is contained in at least \(\frac{N}{n + 1}\) pairs (a, b) with \(a \in A\) such that \(z \in S(a, b)\).

This gives a total of at least \(\frac{NM}{(n + 1)}\) ordered pairs \(a \in A, b \in B\) such that \(z \in S(a, b)\), as desired. \(\square \)

3 Positive-fraction results for t-shapes

Before proving Theorem 1.2, notice that it can be naturally extended to measures in \(\mathbb {R}^n\) by usual approximation arguments.

Theorem 3.1

There exist positive absolute constants \({c_1}\) and \(c_2\) satisfying the following property. For every t-shape S(x, y) in \(\mathbb {R}^n\) and for every Borel probability measure \(\mu \) in \(\mathbb {R}^n,\) setting

$$\begin{aligned} \lambda = c_1 \cdot t \cdot c_2^n \end{aligned}$$

guarantees that there is a point \(z \in \mathbb {R}^n\) such that

$$\begin{aligned} {\mathbb {P}}(z \in S(x,y): x,y \ \hbox {are independent } \mu \text {-random points}) \ge \lambda . \end{aligned}$$

We now prove Theorem 1.2 (and thus Theorem 3.1 as well). The first ingredient we need is the following lemma.

Lemma 3.2

Let \((X, \rho )\) be a finite metric spaces with \(|X| = N > 1\). Then,  there is a subset \(Y \subset X\) such that one can find at least \(N^2/64\) ordered pairs (y, x) with \(y \in Y,\) \(x \in X {\setminus } Y\) and \(\rho (x,y) \ge \frac{1}{4} {{\mathrm{diam}}}{Y}\).

Proof

Let \(B_r(x)\) be the closed \(\rho \)-ball in X of radius r centered at x. For each \(x \in X\) let

$$\begin{aligned} a(x) = \max \left\{ r \in \mathbb {R}_+ : | B_r(x)| \le \frac{3N}{4}\right\} . \end{aligned}$$

We can enumerate the points of X as \(x_1, x_2, \ldots , x_N\) so that

$$\begin{aligned} a(x_1) \le a(x_2) \le \cdots \le a(x_N). \end{aligned}$$

We will prove that the set \(Y = \{x_i : i \le \lfloor \frac{3N}{4} \rfloor \}\) satisfies the conclusion of the lemma.

Set \(a = a (x_{ \left\lfloor {3N}/4 \right\rfloor })\). First we show that \({{\mathrm{diam}}}{Y} \le 2a\). Indeed, for every two points \(y_1, y_2 \in Y\) the sets

$$\begin{aligned} B_{a(y_1)}(y_1) \cap X \quad \text {and} \quad B_{a(y_2)}(y_2) \cap X \end{aligned}$$

are each of cardinality at least \(\frac{3N}{4}\) and thus have a point of intersection z. Then

$$\begin{aligned} \rho (y_1, y_2) \le \rho (y_1,z) + \rho (z,y_2) \le a(y_1) + a(y_2) \le 2a. \end{aligned}$$

Now consider the graph \(G=(V,E)\) with vertex set \(V=X {\setminus } Y\) such that two points \(v_1, v_2 \in V\) are connected if and only if \(\rho ( v_1, v_2) \ge a\). Let \(\alpha (G)\) be the independence number of G. We consider two cases that cover all possibilities.

Case 1. \(\alpha (G) \le \frac{N}{8}\). We will show that for every \(y \in Y\) there are at least N / 8 pairs (y, v) such that \(v \in V\) and \(\rho (y,v) \ge a/2\).

Assume the opposite: for some \(y \in Y\) there are fewer than N / 8 pairs (y, v) with \(v \in V\) such that \(\rho (y,v) \ge a/2\). From the assumption it follows that for more than \(|V| - N/8\) points \(v\in V\) the inequality \(\rho (y,v) < a/2\) holds. We can choose \(\varepsilon > 0\) to be small enough to satisfy the following condition: for every \(v \in V\) one has \(\rho (y,v) \le a/2 - \varepsilon \) whenever \(\rho (y,v) < a/2\). Hence \(|V \cap B_{a/2 - \varepsilon }(y)| > |V| - N/8\).

On the other hand,

$$\begin{aligned} |V| = N - |Y| = N- \left\lfloor \frac{3N}{4}\right\rfloor \ge \frac{N}{4}. \end{aligned}$$

Hence \(|V \cap B_{a/2 - \varepsilon }(y)| > \frac{N}{4} - \frac{N}{8} = \frac{N}{8}\). By definition of Case 1, the set \(V \cap B_{a/2 - \varepsilon }(y)\) is too large to be independent in G. But \({{\mathrm{diam}}}B_{a/2 - \varepsilon }(y) < a\), and therefore the set \(V \cap B_{a/2 - \varepsilon }(y)\) has to be independent in G, a contradiction.

So, there are at least \(\frac{N}{8} \cdot \left\lfloor \frac{3N}{4} \right\rfloor \) pairs (y, v) such that \(y \in Y, v\in V\) and \(\rho (y,v) > a/2\), which is sufficient for the lemma.

Case 2. \(\alpha (G) > \frac{N}{8}\). Let \(W \subset V\) be an independent set in G with \(|W| > \frac{N}{8}\).

First notice that, by the choice of Y and V, each point \(v \in V\) satisfies

$$\begin{aligned} |X {\setminus } B_{a-\epsilon }(v)| \ge \lceil N/4 \rceil \end{aligned}$$

for every \(\varepsilon \in (0, a)\).

Fix a point \(w \in W\). Choose \(\varepsilon \in (0, a)\) to be small enough to satisfy the following condition: for every \(x \in X\) one has \(\rho (w, x) \le a - \varepsilon \) whenever \(\rho (w, x) < a\).

For every \(w' \in W\) (\(w' \ne w\)), the vertices w and \(w'\) are not connected by an edge of G. Thus \(\rho (w, w') < a\), and, consequently, \(\rho (w, w') \le a - \varepsilon \). Hence \(W \subset B_{a - \varepsilon }(w)\).

Therefore

$$\begin{aligned} X {\setminus } B_{a - \varepsilon }(w) = (V{\setminus } B_{a - \varepsilon }(w)) \cup (Y {\setminus } B_{a - \varepsilon }(w)) \subset (V{\setminus } W) \cup (Y {\setminus } B_{a - \varepsilon }(w)). \end{aligned}$$

As a result, we have

$$\begin{aligned} |X {\setminus } B_{a - \varepsilon }(w)| \le |Y {\setminus } B_{a - \varepsilon }(w)| + |V{\setminus } W| = |Y {\setminus } B_{a - \varepsilon }(w)| + |V| - |W|, \end{aligned}$$

and so

$$\begin{aligned} |Y {\setminus } B_{a - \varepsilon }(w)| \ge |X {\setminus } B_{a - \varepsilon }(w)| + |W| - |V| \ge \lceil N/4 \rceil + N/8 - \lceil N/4 \rceil = N/8. \end{aligned}$$

Thus, every \(w \in W\) produces at least \(\frac{N}{8}\) pairs (y, w) with \(y \in Y\) and \(\rho (y,w) > a - \varepsilon \). By the choice of \(\varepsilon \), all such y satisfy \(\rho (y,w) \ge a\) as well. Iterating over all \(w \in W\), we get a total of at least \(\frac{N}{8} \cdot \frac{N}{8} = \frac{N^2}{64}\) pairs (y, x) (where \(x = w\)) for the lemma. \(\square \)

We are now ready to prove Theorem 1.2.

Proof of Theorem 1.2

Let \(U_n\) be the volume of the unit ball in \(\mathbb {R}^n\).

For the set \(X \subset \mathbb {R}^n\), choose a subset Y which satisfies the conditions of Lemma 3.2. Let \(d = {{\mathrm{diam}}}{Y}\).

Define

$$\begin{aligned} R = \bigcup _{y \in Y} B_d(y). \end{aligned}$$

Note that \(Y \subset B_d(y)\) for any \(y \in Y\). As a consequence, \(R \subset B_{2d}(y)\). Thus, \({{\mathrm{Vol}}}(R) \le (2d)^n U_n\).

On the other hand, for all pairs (y, x) with \(y \in Y\), \(x \in X {\setminus } Y\) and \(|x-y| > \frac{d}{4}\) one has

$$\begin{aligned} {{\mathrm{Vol}}}{(S(x,y) \cap R)} \ge t \cdot \frac{d^n}{4^n} \cdot U_n. \end{aligned}$$

Since the number of such pairs is at least \(\frac{N^2}{64}\), there is a point in R that is covered by at least

$$\begin{aligned} \frac{t*(d^n/4^n)*U_n}{{{\mathrm{Vol}}}(R)}\cdot \frac{N^2}{64} \ge \frac{t \cdot N^2}{2^n \cdot 4^{n+3}} \end{aligned}$$

sets of the form S(x, y). Hence Theorem 1.2 is proved with \(c_1 = 1/64\), \(c_2 = 1/8\). \(\square \)

4 Positive-fraction result for boxes

A box is a (closed) parallelotope with all edges parallel to coordinate axes. For arbitrary \(t > 0\) a box is not a t-shape, because it can be arbitrarily flat along any coordinate plane. Nevertheless, we prove a positive-fraction result for boxes.

Theorem 4.1

For each \(x,y \in \mathbb {R}^n\) let S(x, y) be the minimal box that contains x and y. Then, 

  • for any finite set \(X \subset \mathbb {R}^n\) of N points,  there is a point covered by at least \(\frac{N}{2^n}( \frac{N}{2^n} - 1)\) sets of the form S(x, y) with \(x,y \in X,\) and

  • for each \(\varepsilon > 0,\) there is a finite set \(X \subset \mathbb {R}^n\) of N points such that no point is contained in more than \((\frac{1}{2^n}+\varepsilon )N^2\) sets of the form S(x, y) with \(x,y \in X\).

For a point \(x \in \mathbb {R}^n\), we denote by \((x_1, x_2, \ldots , x_n)\) its coordinates. We prove Theorem 4.1 via the following lemma.

Lemma 4.2

Let \(X\subset \mathbb {R}^n\) be a set of N points, \(j \in \{ 1, 2, \ldots , n \}\). Then there exist two sequences

$$\begin{aligned} z_1, z_2, \ldots , z_j \; (z_i \in \mathbb {R}) \quad \text {and} \quad \varepsilon _1, \varepsilon _2, \ldots , \varepsilon _j \; (\varepsilon _i \in \{ -1, +1 \}) \end{aligned}$$

such that the two sets

$$\begin{aligned} R_1= & {} \{ x \in \mathbb {R}^n : \varepsilon _i(x_i - z_i) \le 0 \; \text {for} \; i = 1, 2, \ldots , j \}, \\ R_2= & {} \{ x \in \mathbb {R}^n : \varepsilon _i(x_i - z_i) \ge 0 \; \text {for} \; i = 1, 2, \ldots , j \} \end{aligned}$$

satisfy \(|X \cap R_k| \ge \frac{|X|}{2^j}\) for \(k = 1,2\).

Proof

We use induction over j. Let \(j = 1\) and choose \(z_1\) so that the plane \(x_1 = z_1\) splits the set X into almost equal parts (this, by definition, means that the intersection of X with each of two closed subspaces \(x_1 \le z_1\) and \(x_1 \ge z_1\) contains at least |X| / 2 points). It is clear that \(\varepsilon _1 = +1\) will suffice.

Let \(j > 1\). By induction hypothesis, we can find \(z_1, z_2, \ldots , z_{j - 1}\) and \(\varepsilon _1, \varepsilon _2, \ldots , \varepsilon _{j - 1}\) that satisfy the statement for \(j - 1\). Set

$$\begin{aligned} X_1^{(j - 1)}= & {} X \cap \{ x \in \mathbb {R}^n : \varepsilon _i(x_i - z_i) \le 0 \text { for }i = 1, 2, \ldots , j - 1 \},\\ X_2^{(j - 1)}= & {} X \cap \{ x \in \mathbb {R}^n : \varepsilon _i(x_i - z_i) \ge 0 \text { for }i = 1, 2, \ldots , j - 1 \}. \end{aligned}$$

The inductive assumption implies that

$$\begin{aligned} |X_k^{(j - 1)}| \ge \frac{|X|}{2^{j - 1}} \quad \text {for }k = 1, 2. \end{aligned}$$

For \(k = 1, 2\) choose \(z_j^{(k)}\) so that the plane \(x_j = z_j^{(k)}\) splits the set \(X_k^{(j - 1)}\) into almost equal parts. Now set \(z_j = \frac{z_j^{(1)} + z_j^{(2)}}{2}\), and \(\varepsilon _j = +1\) if \(z_j^{(1)} < z_j^{(2)}\), or \(\varepsilon _j = -1\) otherwise. This is sufficient to complete the induction step. \(\square \)

Proof of Theorem 4.1

Apply Lemma 4.2 to the set X with \(j = n\). Set \(z = (z_1, z_2, \ldots , z_n)\), \(X_1 = X \cap R_1\), \(X_2 = (X \cap R_2) {\setminus } \{ z \}\). For every \(x_1 \in X_1\) and every \(x_2 \in X_2\) the box \(S(x_1, x_2)\) contains z.

Further, \(|X_1| \ge \frac{N}{2^n}\), \(|X_2| \ge \frac{N}{2^n} - 1\) and \(X_1 \cap X_2 = \emptyset \), which gives the necessary number of pairs.

For the lower bound, notice that by standard approximation arguments (see, for instance, [18]) it suffices to find a probability measure \(\mu \) in \(\mathbb {R}^n\) which is absolutely continuous with respect to the Lebesgue measure such that for all \(z \in \mathbb {R}^n\), the probability that \(z \in S(x,y)\) is at most \(\frac{1}{2^n}\) where x, y are independent \(\mu \)-random points. Let \(\mu \) be the uniform probability measure on the unit cube \(C=[0,1]^n\).

Given \(z=(z_1, z_2, \ldots , z_n)\) and \(x,y \in \mathbb {R}^n\), notice that \(z \in S(x,y)\) if and only if there is a sequence \(a=(\varepsilon _1, \varepsilon _2, \ldots , \varepsilon _n)\in \{+1,-1\}^n\) such that

$$\begin{aligned} x \in R^{a}_1= & {} \{ u \in \mathbb {R}^n : \varepsilon _i(u_i - z_i) \le 0 \text { for }i = 1, 2, \ldots , n \}, \\ y \in R^{a}_2= & {} \{ u \in \mathbb {R}^n : \varepsilon _i(u_i - z_i) \ge 0 \text { for }i = 1, 2, \ldots , n \} \end{aligned}$$

Thus

$$\begin{aligned} {\mathbb {P}}[z \in S(x,y): x,y \hbox { i.i.d.}] = \sum _{a \in \{+1,-1\}^n} {{\mathrm{Vol}}}(R^{a}_1 \cap C) \cdot {{\mathrm{Vol}}}(R^a_2 \cap C) \end{aligned}$$

Also, if \(z \in S(x,y)\) for any x, y, it is necessary that \(0 \le z_i \le 1\). In order to bound \({{\mathrm{Vol}}}(R^{a}_1 \cap C) \cdot {{\mathrm{Vol}}}(R^a_2 \cap C)\), we may assume without loss of generality that \(a = (+1,+1,\ldots , +1)\). Then

$$\begin{aligned} {{\mathrm{Vol}}}(R^{a}_1 \cap C) \cdot {{\mathrm{Vol}}}(R^a_2 \cap C)= & {} \left( \prod _{i=1}^n z_i \right) \left( \prod _{i=1}^n (1-z_i)\right) \\= & {} \prod _{i=1}^n z_i (1-z_i) \le \prod _{i=1}^n \frac{1}{4} = \frac{1}{4^n} \end{aligned}$$

which gives us the desired conclusion.

$$\begin{aligned} P[z \in S(x,y): x,y \ \text{ i.i.d. }] = \sum _{a \in \{+1,-1\}^n} {{\mathrm{Vol}}}(R^{a}_1 \cap C) \cdot {{\mathrm{Vol}}}(R^a_2 \cap C) \le \frac{1}{2^n} \end{aligned}$$

\(\square \)

5 Results for weak \(\varepsilon \)-nets

In this section we show that the notion of weak \(\varepsilon \)-nets can be extended to operators other than the convex hull. The arguments we use are based on the original proof in [1].

The first topological extension of the first selection lemma in arbitrary dimension, stated below, was obtain by Gromov [13], which extends to continuous maps.

Theorem

Let \(\Delta ^{N-1}\) be the \((N-1)\)-dimensional simplex and \(f:\Delta ^{N-1} \rightarrow \mathbb {R}^n\) a continuous map. There is a constant \(c_{n}^*\) depending only on n such that we can always find a family \(\mathcal {F}\) of n-dimensional faces of \(\Delta ^{N-1}\) such that the images of \(\mathcal {F}\) intersect and

$$\begin{aligned} |\mathcal {F}| \ge c_n^* \left( {\begin{array}{c}N\\ n+1\end{array}}\right) \end{aligned}$$

Moreover, 

$$\begin{aligned} c_n^* \ge \frac{2n}{(n+1)(n+1)!} \end{aligned}$$

There are now improved bounds on \(c_n^*\) [17] (see also [21]). When f is linear, we obtain the classic version of the first selection lemma. A simplified proof of the result above is contained in [15]. Using this result, one can prove a topological version of the weak \(\varepsilon \)-net result of [1] with an analogous proof.

Theorem 5.1

Let n be a positive integer,  \(\varepsilon >0\). Then,  there is a positive integer \(m_{{\text {top}}} = m_{{\text {top}}} (n, \varepsilon )\) such that the following holds. For a positive integer N,  let \(\Delta ^{N-1}\) be the \((N-1)\)-dimensional simplex,  with N vertices. For every \(N \ge \varepsilon ^{-1}(d+1)\) and every continuous map \(f:\Delta ^{N-1} \rightarrow \mathbb {R}^n,\) there is a set \({\mathcal {T}} \subset \mathbb {R}^n\) of at most m points such that the following holds. For any set \(A \subset \Delta ^{N-1}\) of at least \(\varepsilon N\) vertices, 

$$\begin{aligned} f[\langle A \rangle ] \cap {\mathcal {T}} \ne \emptyset \end{aligned}$$

where \(\langle A \rangle \) denotes the face of \(\Delta ^{N-1}\) generated by A. Moreover,  \(m_{{\text {top}}} = O(\varepsilon ^{-n-1})\) where the implied constant of the O notation depends on n.

Proof of Theorem 5.1

We construct the set \({\mathcal {T}}\) inductively, by counting the number K of faces B of size \(n+1\) such that \(f[\langle B\rangle ] \cap {\mathcal {T}} = \emptyset \). Suppose there is a face A with \(|A| \ge \varepsilon N\) such that \(f[\langle A \rangle ] \cap {\mathcal {T}} = \emptyset \). Then, by the topological version of the first selection lemma applied to A, there must be a point \(t \in \mathbb {R}^n\) such that \(t \in f[\langle B \rangle ]\) for at least

$$\begin{aligned} c^*_n \left( {\begin{array}{c}\varepsilon N\\ n+1\end{array}}\right) \sim \varepsilon ^{n+1}c^*_n \left( {\begin{array}{c}N\\ n+1\end{array}}\right) \end{aligned}$$

different subsets \(B \subset A\) with \(|B|=n+1\). Thus, by adding the point t to \({\mathcal {T}}\), we have reduced K by at least \(\varepsilon ^{n+1}c^*_n \left( {\begin{array}{c}N\\ n+1\end{array}}\right) \). This process cannot be repeated more than \((\varepsilon ^{n+1}c^*_n)^{-1}\) times, so we obtain \(m_{{\text {top}}} \le (\varepsilon ^{n+1}c^*_n)^{-1}\), as desired. \(\square \)

Even though this result and its proof are natural with current methods, it seems that this generalisation has not yet been observed. The proof of Theorem 1.3 is almost identical, but we include it for the sake of completeness.

Proof of Theorem 1.3

We construct the set \({\mathcal {T}}\) inductively, by counting the number K of pairs \(\{x,y\} \in \left( {\begin{array}{c}X\\ 2\end{array}}\right) \) such that \(S(x,y) \cap {\mathcal {T}} = \emptyset \). Suppose there is a subset A with \(|A|\ge \varepsilon |X|\) such that \({\text {thin}}_S (A) \cap {\mathcal {T}} = \emptyset \). Then, by Theorem 1.2 applied to A, there must be a point \(p \in \mathbb {R}^n\) such that \(t \in S(x,y)\) for at least

$$\begin{aligned} \lambda (\varepsilon |X|)^2 \ge 2\lambda \varepsilon ^2 \left( {\begin{array}{c}|X|\\ 2\end{array}}\right) \end{aligned}$$

ordered pairs \((x,y) \in A \times A\). Thus, by adding the point p to \({\mathcal {T}}\), we have reduced K by at least \(\lambda \varepsilon ^2 \left( {\begin{array}{c}|X|\\ 2\end{array}}\right) \). This process cannot be repeated more than \((\lambda \varepsilon ^2)^{-1}\) times, giving the desired bound. \(\square \)

The same proof method has been used to get other extensions of weak \(\epsilon \)-nets for convex sets, such as quantitative versions in [24]. When we apply Theorem 1.3 to \(\alpha \)-lenses (Example 1 in the introduction), we obtain the following corollary.

Corollary 1

For any two real numbers \(\alpha \in [0, \pi ),\) \(\varepsilon \in (0,1]\) and a positive integer n,  there is an integer \(m' = m'(n, \varepsilon , \alpha )\) such that the following holds. For every finite set \(S \subset \mathbb {R}^n,\) there is a set \({\mathcal {T}} \subset \mathbb {R}^n\) of \(m'\) points such that if \(A \subset S\) is a subset of at least \(\varepsilon |S|\) points,  then there are \(x,z \in A\) and \(y\in {\mathcal {T}}\) such that

$$\begin{aligned} \angle xyz > \alpha . \end{aligned}$$

Moreover,  \(m' = O(\varepsilon ^{-2}),\) where the implied constant of the O notation depends on n and \(\alpha \).

In other words, there is a point of \({\mathcal {T}}\) that sees some pair of points of every large subset of S at a wide angle. It is surprising that this notion of being close to S allows for weak \(\varepsilon \)-nets of such small size.

This would be a counterpart to [5, Theorem 4]. In that result, Bárány and Lehel showed that for every angle \(\alpha < \pi \) and every compact set \(V \subset \mathbb {R}^d\) has a subset S of fixed size (depending only on d and \(\alpha \)) such that every point in X “sees” some pair of points of S at an angle wider than \(\alpha \). In other words, if we denote by the \(\alpha \)-lens of \(\{x,y\}\) the set of points z such that \(\angle xzy > \alpha \), it says that a fixed number of \(\alpha \)-lenses of C cover the points in C. In our result, we show that given the set C, a fixed number of points intersects “most” of the \(\alpha \)-lenses of C.