betaFeedback

WorksComputer Science

Strong Lower Bounds for Weak Epsilon-Nets

Abstract

Let PP be a finite point set in Rd\mathbb{R}^d. A weak ε\varepsilon-net for PP with respect to convex sets is a finite set X⊂RdX\subset\mathbb{R}^d intersecting every convex set containing at least ε∣P∣\varepsilon|P| points of PP. Determining their optimal worst-case size was described by Alon, Kalai, Matousek, and Meshulam [Adv. Appl. Math., 2002] as "one of the truly important open problems in combinatorial geometry." We give elementary constructions which establish the first polynomially superlinear lower bounds in fixed dimension. Already in R3\mathbb{R}^3, we construct point sets for which every weak ε\varepsilon-net has size Ω(ε−3/2)Ω(\varepsilon^{-3/2}). More generally, for every fixed d≥3d\ge3, we obtain a lower bound of Ωd(ε−γd)Ω_d(\varepsilon^{-γ_d}), where γd=d/2+O(1)γ_d=\sqrt{d/2}+O(1). Consequently, no upper bound of the form Od(ε−C)O_d(\varepsilon^{-C}) can hold with an absolute constant CC which is independent of the dimension. Despite the recent progress on upper bounds, the strongest previous general lower bound remained Ωd(ε−1log⁡d−1(1/ε))Ω_d(\varepsilon^{-1}\log^{d-1}(1/\varepsilon)), due to Bukh, Matousek, and Nivasch [Israel J. Math., 2011]. To obtain our results, we apply a quadratic lift to grid-based configurations with many point-line incidences. The bounds also yield polynomial separations between fractional and integral piercing numbers of convex families, and lower bounds for Hadwiger-Debrunner numbers.

Introduction

The theory of ε\varepsilon-nets plays a foundational role in discrete and computational geometry, learning theory, and high-dimensional probability, among other areas; see, e.g., [20, 6, 28]. Haussler and Welzl introduced the notions of strong and weak ε\varepsilon-nets in their seminal work on geometric range searching in the 1980s [15, 16]. Let R\mathcal{R} be a family of subsets of Rd\mathbb{R}^{d}, let P⊂RdP \subset\mathbb{R}^{d} be a finite nonempty point set, and let 0<ε≤10 < \varepsilon\le1. A strong ε\varepsilon-net for PP with respect to R\mathcal{R} is a set X⊆PX \subseteq P that pierces every range R∈RR \in\mathcal{R} containing at least ε∣P∣\varepsilon|P| points of PP. A weak ε\varepsilon-net satisfies the same piercing requirement but allows the points of XX to lie anywhere in Rd\mathbb{R}^{d}. We study weak ε\varepsilon-nets for convex ranges. We denote by Cε\mathcal{C}_{\varepsilon} the family of all convex sets containing at least ε∣P∣\varepsilon|P| points of PP.

Many families of convex ranges, such as halfspaces or balls in fixed dimension, admit strong ε\varepsilon-nets whose size is independent of ∣P∣|P|. This follows from the classical ε\varepsilon-net theorem. Every finite range space of Vapnik–Chervonenkis (VC) dimension δ\delta admits a strong ε\varepsilon-net of size O((δ/ε)log⁡(1/ε))O((\delta/\varepsilon)\log(1/\varepsilon)), for 0<ε≤1/20 < \varepsilon\le1/2 [15, 16, 17]. This bound is optimal in general. For every fixed δ≥2\delta\ge2 and sufficiently small ε\varepsilon, there are range spaces of VC dimension at most δ\delta in which every strong ε\varepsilon-net has size Ω((δ/ε)log⁡(1/ε))\Omega((\delta/\varepsilon)\log(1/\varepsilon)) [17]. Thus, bounded VC dimension guarantees strong ε\varepsilon-nets of size nearly linear in 1/ε1/\varepsilon, and the logarithmic factor cannot be removed in general.

On the other hand, arbitrary convex ranges exhibit a fundamentally different situation. In every dimension d≥2d \ge2, the family of all convex sets has unbounded VC dimension. For instance, consider a set PP of nn points in convex position; then conv⁡(S)∩P=S\operatorname{conv}(S) \cap P = S for every subset S⊆PS \subseteq P. Consequently, any set X⊆PX \subseteq P with at most n−⌈εn⌉n-\lceil\varepsilon n\rceil points misses the convex hull of P∖XP \setminus X, which contains at least εn\varepsilon n input points; see Figure 1. Every strong ε\varepsilon-net for such a configuration therefore requires at least n−⌈ϵn⌉+1n-\lceil\epsilon n\rceil+1 points. For any fixed ϵ<1\epsilon< 1, this rules out a bound independent of nn.

Three configurations of points in convex position and heavy convex sets

Figure 1. For nn points in convex position, any candidate strong ϵ\epsilon-net XX with ∣X∣≤n−⌈ϵn⌉|X| \le n-\lceil\epsilon n\rceil misses the heavy convex set conv⁡(P∖X)\operatorname{conv}(P \setminus X).

Allowing net points outside PP can dramatically reduce the number of points required, even in the plane. Let PP consist of the vertices of a regular nn-gon centered at the origin, where n≥4n \ge4 is even, and set ϵ=(n/2+1)/n\epsilon=(n/2+1)/n. Every convex set containing at least ϵn\epsilon n vertices contains an antipodal pair and hence the origin. Thus, the origin alone forms a weak ϵ\epsilon-net, whereas the preceding argument shows that every strong ϵ\epsilon-net contains at least n/2n/2 points; see Figure 2.

Three configurations of vertices of a regular even polygon and the origin

Figure 2. For the vertices of a regular even nn-gon and ϵ=(n/2+1)/n\epsilon=(n/2+1)/n, the origin alone forms a weak ϵ\epsilon-net, while every strong ϵ\epsilon-net requires at least n/2n/2 points.

Throughout the paper, we write r:=1/ϵ≥1r:=1/\epsilon\ge1 and discuss weak 1/r1/r-nets. For a finite nonempty set P⊂RdP\subset\mathbb{R}^{d}, let fd(P,r)f_d(P,r) denote the minimum cardinality of a weak 1/r1/r-net for PP with respect to all convex ranges in Rd\mathbb{R}^{d}. We define the corresponding worst-case size by

fd(r):=sup⁡{fd(P,r):P⊂Rd is finite and nonempty}.f_d(r):=\sup\{f_d(P,r):P\subset\mathbb{R}^{d}\text{ is finite and nonempty}\}.

A fundamental theorem of Alon, Bárány, Füredi, and Kleitman shows that fd(r)f_d(r) is bounded by a polynomial in rr for every fixed dimension dd [ABFK92]. Thus, despite the unbounded VC dimension of convex ranges, convexity guarantees weak nets whose size is independent of the number of input points.

Weak ϵ\epsilon-nets also provide a fundamental link between fractional and integral piercing of convex sets. A fractional piercing assigns nonnegative weights to finitely many points so that every set in a given convex family receives total weight at least one. If the total weight is tt, normalization makes every set 1/t1/t-heavy under the resulting probability distribution. A weak net for this distribution then pierces the entire family. Bounds on weak nets therefore control the cost of converting fractional solutions into actual piercing sets [4]. In fact, this passage is a central step in Alon and Kleitman’s proof of the Hadwiger–Debrunner (p,q)(p,q)-theorem, which combines fractional Helly theory with weak nets to deduce bounded piercing numbers from local intersection conditions [3]. Reflecting on the importance of this quantitative problem, Alon, Kalai, Matoušek, and Meshulam in their seminal work [4] wrote:

“Finding the correct estimates for weak ϵ\epsilon-nets is, in our opinion, one of the truly important open problems in combinatorial geometry”.

The search for sharp bounds has generated a sustained and long line of work spanning more than three decades. The original theorem of Alon, Bárány, Füredi, and Kleitman gave the planar bound f2(r)=O(r2)f_2(r)=O(r^2) [ABFK92]. In higher dimensions, Chazelle, Edelsbrunner, Grigni, Guibas, Sharir, and Welzl obtained

fd(r)=Od(rdlog⁡d−1r),f_d(r)=O_d\left(r^d\log^{d-1}r\right),

where cdc_d depends only on dd, in work first presented at STOC 1993 [10]. Subsequently, Matoušek and Wagner gave a simpler construction using simplicial partitions [21]. These bounds resisted any improvements in their polynomial exponents for more than two decades. Rubin finally broke the quadratic barrier in the plane at FOCS 2018 by proving f2(r)=Oη(r3/2+η)f_2(r) = O_{\eta}(r^{3/2+\eta}) for every fixed η>0\eta> 0 [23]. In a subsequent work [24] at STOC 2021, Rubin improved the exponent below dd in every fixed dimension d≥3d \ge3. See Table 1 for the precise exponents he attained.

Dimension ddLower bound for fd(r)f_d(r)Upper bound for fd(r)f_d(r)
2Ω(rlog⁡r)\Omega(r\log r) [7]O(r1.5+δ)O(r^{1.5+\delta}) [23]
3O(r2.558+δ)O(r^{2.558+\delta}) [25]
4Ω(r1.5)\Omega(r^{1.5})O(r3.480+δ)O(r^{3.480+\delta}) [25]
5Ω(r1.5)\Omega(r^{1.5})O(r4.437+δ)O(r^{4.437+\delta}) [25]
6Ω(r1.5)\Omega(r^{1.5})O(r5.450+δ)O(r^{5.450+\delta}) [25]
7Ω(r2)\Omega(r^2)O(r6.459+δ)O(r^{6.459+\delta}) [25]
⋮\vdotsΩ(r2)\Omega(r^2)⋮\vdots
12Ω(r2.5)\Omega(r^{2.5})O(r11.478+δ)O(r^{11.478+\delta}) [25]
⋮\vdotsΩ(r2.5)\Omega(r^{2.5})⋮\vdots

Table 1. Table of current best lower and upper bounds for fd(r)f_d(r). New results in this paper are written in red. The existing upper bounds4 hold for an arbitrary value δ>0\delta> 0.

These advances substantially reduced the upper bounds, while leaving a large gap from the known lower bounds. Bukh, Matoušek, and Nivasch, in their seminal work [7] (see also [8]) at SoCG 2009, established

fd(r)=Ωd(rlog⁡d−1r)f_d(r) = \Omega_d(r\log^{d-1} r)

for every fixed d≥2d \ge2, which gave the first superlinear lower bound in fixed dimension. This remained the strongest general lower bound prior to our work. Although their result ruled out linear-size weak nets, its improvement over the linear bound was only polylogarithmic in every fixed dimension.

The gap therefore left open a basic and fundamental question about the growth of fd(r)f_d(r). Could weak nets always have size r1+o(1)r^{1+o(1)} in every fixed dimension, or does some fixed dimension require polynomially superlinear size? Despite the upper bounds having exponents that grow with dd, no lower bound of the form Ω(r1+δ)\Omega(r^{1+\delta}), for a fixed δ>0\delta> 0, was known in any fixed dimension.

Our results

Theorem 1. For every integer d≥3d \ge3, define

γd:=12⌊8d+25−12⌋.\gamma_d := \frac{1}{2}\left\lfloor\frac{\sqrt{8d+25}-1}{2}\right\rfloor.

There exist constants rd>0r_d > 0 and cdc_d, such that for every r≥rdr \ge r_d there is a point set P⊂RdP \subset\mathbb{R}^d for which every weak rr-net with respect to convex sets has at least cdrγdc_d r^{\gamma_d} points. Consequently fd(r)=Ωd(rγd)f_d(r) = \Omega_d(r^{\gamma_d}).

The following table illustrates the dimensions required to obtain the first few distinct values of γd\gamma_d.

The starting point for our theorem is to apply a quadratic lift ψ(x,y)=(x,y,x2,xy)\psi(x,y)=(x,y,x^2,xy) to a configuration of points P0P_0 on a 2D grid following Elekes’ [11] construction with many point-line incidences. Define PLIFTED=ψ(P0)P_{\mathrm{LIFTED}}=\psi(P_0). For every 2D line ℓ\ell, the lifted points ψ(ℓ∩P0)\psi(\ell\cap P_0) are in convex position. We examine the 2D qq-rich lines ℓ\ell that contain many 2D points of P0P_0, and 4D convex hulls of point sets that contain exactly q/2q/2 points of ψ(ℓ∩P0)\psi(\ell\cap P_0). We show that it is difficult to construct a weak net that hits all such 4D convex hulls. It can be proved that points of a weak net that are not points of PLIFTEDP_{\mathrm{LIFTED}} can only pierce convex sets originating from a unique line. We can replace points in the net that are not in the original point set by a small number (determined by the line richness) of lifted points to obtain a strong net. However, a strong net for the lift of points along a line is a strong net for points in convex position, and thus must be large. By a simple counting argument the strong net, and the weak net must also be large. This yields a lower bound of Ω(r1.5)\Omega(r^{1.5}) in 4D.

We can reduce the dimensionality of the lower bound to 3D by slightly shifting the grid before performing a modified lift ϕ(x,y)=(x2,xy,y2)\phi(x,y)=(x^2,xy,y^2). This allows for a point in a weak net to pierce convex sets arising from multiple lines. The shift ensures every 4D point outside the lifted grid pierces convex sets arising from at most four distinct 2D lines. This generalizes to higher dimensions where we take the quadratic lift of a higher dimensional grid. To be precise we lift an s+1s+1 dimensional grid to s−1+(s+22)=(s2+5s)/2s-1+\binom{s+2}{2}=(s^2+5s)/2 dimensions.

The quadratic lift is essential in our construction since we need to deal with the convex combination of lifted points that originated from a single hyperplane. The crucial idea is that the convex combination allows us to solve for the defining equation of the hyperplane. We are unable to see how to avoid lifting to quadratically many dimensions, as all coordinates of the lift are needed for the hyperplane recovery step. The idea of using quadratic lifts is not new. A similar idea was used for geometric data structure lower bounds by Erickson [12 Section 8], that employed a quadratic Veronese map that sends p=(p1,…,pm)p=(p_1,\ldots,p_m) to the vector (pipj)1≤i≤j≤m(p_i p_j)_{1\leq i\leq j\leq m} of all pairwise coordinate products. The quadratic Veronese map was used to turn incidence bounds into halfspace relations. Afshani [2] used a similar map for slabs.

Applications

Our constructions also have consequences for related fundamental problems in discrete geometry. They yield lower bounds for Hadwiger–Debrunner numbers, which quantify the number of piercing points guaranteed by local intersection conditions. Our results also yield polynomial separations between fractional and integral piercing numbers, which establish lower bounds on the integrality gap of the standard linear programming relaxation for minimum piercing set.

(p,q)(p,q)-Theorem and Hadwiger-Debrunner numbers

A family of sets FF satisfies the (p,q)(p,q)-property if every among any pp sets in FF, there are qq sets which share a non-empty intersection. It was posed by Hadwiger and Debrunner [14] whether every family of convex sets in Rd\mathbb{R}^d with p≥q≥d+1p\geq q\geq d+1 satisfying the (p,q)(p,q)-property can be pierced by a set of points whose size depends only on dd, pp, and qq. Alon and Kleitman [3] prove this in their celebrated (p,q)(p,q)-theorem. This value is known as the Hadwiger-Debrunner number and is denoted by HDd(p,q)\mathrm{HD}_d(p,q). To be precise the Hadwiger–Debrunner number HDd(p,q)\mathrm{HD}_d(p,q) is the least integer NN such that every finite family of nonempty convex sets in Rd\mathbb{R}^d, with at least pp members and satisfying the (p,q)(p,q)-property, can be pierced by at most NN points.

A sequence of work by Keller and Smorodinsky [18] and Roche-Newton [22] use the general position construction of Balogh and Solymosi [9] to show HD2(p,3)≥Ω(p6/5−ε)\mathrm{HD}_2(p,3)\geq\Omega(p^{6/5-\varepsilon}). In higher dimensions, Keller and Smorodinsky [19] utilized the higher dimensional general position constructions of Suk and Zeng [27] that show that for d≥3d\geq3, that HDd(p,d+1)≥Ω(p2−ε)\mathrm{HD}_d(p,d+1)\geq\Omega(p^{2-\varepsilon}) for any ε>0\varepsilon>0.

Lower bounds for weak ε\varepsilon-nets transfer directly to Hadwiger–Debrunner numbers [13, 18]. Indeed, given a finite point set PP, let C\mathcal{C} be the family of convex hulls of subsets of PP containing at least (q/p)∣P∣(q/p)|P| points. Among any pp members of C\mathcal{C}, a simple counting argument shows that there must be a point of PP contained in at least qq of them. Thus this family satisfies the (p,q)(p,q)-property, while every piercing set is a weak (q/p)(q/p)-net with respect to all convex sets. Consequently, HDd(p,q)≥fd(p/q)\mathrm{HD}_d(p,q)\geq f_d(p/q) so a lower bound of the form fd(r)=Ω(g(r))f_d(r)=\Omega(g(r)) implies a lower bound of HDd(p,q)=Ω(g(pq))\mathrm{HD}_d(p,q) = \Omega(g(\frac{p}{q})). The weak net lower bound due to Bukh, Matoušek, and Nivasch [8] results in a lower bound of HDd(p,q)=Ωd(pqlog⁡d−1(pq))\mathrm{HD}_d(p,q) = \Omega_d(\frac{p}{q}\log^{d-1}(\frac{p}{q})). A corollary of our result is a new lower bound for HDd(p,q)\mathrm{HD}_d(p,q).

Corollary 1. For any dimension d≥3d \ge3, and all p≥q≥d+1p \ge q \ge d + 1,

HDd(p,q)=Ωd((pq)γd)whereγd=12⌊8d+25−12⌋.\mathrm{HD}_d(p,q) = \Omega_d\left(\left(\frac{p}{q}\right)^{\gamma_d}\right) \qquad\text{where} \qquad\gamma_d = \frac{1}{2}\left\lfloor\frac{\sqrt{8d+25}-1}{2}\right\rfloor.

We observe that this leads to two refinements of existing lower bounds on HDd(p,q)\mathrm{HD}_d(p,q). The first is that this yields a lower bound where the exponent increases beyond 2 provided d≥12d \ge12. The second is that even if q=pαq = p^\alpha for some constant 0<α<10 < \alpha< 1, in sufficiently high dimension dd, the quantity HDd(p,q)\mathrm{HD}_d(p,q) is superlinear in pp.

Approximating Minimum Piercing Set

For a set system F=(U,S)F = (U,\mathcal{S}), the minimum hitting set is the minimum cardinality set H⊂UH \subset U such that for every S∈SS \in\mathcal{S}, S∩H≠∅S \cap H \ne\varnothing. In this sense, a strong ε\varepsilon-net is a hitting set for the set system (U,Cε)(U,\mathcal{C}_\varepsilon) and a weak ε\varepsilon-net is a hitting set for (Rd,Cε)(\mathbb{R}^d,\mathcal{C}_\varepsilon). Let τ(F)\tau(F) be the cardinality of the minimum hitting set of FF. When U=RdU = \mathbb{R}^d, we will use the term minimum piercing set.

On the positive side, the existence of g(1ε)g(\frac{1}{\varepsilon})-sized strong ε\varepsilon-nets for a given set system implies a polynomial time algorithm which returns a hitting set of size g(4τ(F))g(4\tau(F)), due to Brönnimann and Goodrich [5]. This algorithm relies on the multiplicative weight update paradigm, wherein the weights of a finite set of points PP are modified when the calling to the ε\varepsilon-net construction fails to return a valid hitting set. In the case of approximating a minimum piercing set, all points in Rd\mathbb{R}^d are valid elements to use for hitting and the sets to be hit are the input convex regions Cε\mathcal{C}_\varepsilon. To make the universe finite, assign a representative point from each cell in the arrangement A\mathcal{A} induced by Cε\mathcal{C}_\varepsilon. Weak ε\varepsilon-nets in (Rd,Cε)(\mathbb{R}^d,\mathcal{C}_\varepsilon) therefore correspond to strong ε\varepsilon-nets in the set system (A,Cε)(\mathcal{A},\mathcal{C}_\varepsilon). Thus, Rubin’s [25] upper bound implies polynomial time approximation algorithms that are at worst polynomial in the optimal solution, namely τ(F)O(d)\tau(F)^{O(d)} for fixed dd.

The existence of weak ε\varepsilon-nets for PP with respect to C\mathcal{C} is also intimately related to the linear programming relaxation of minimum piercing set. Here, we use the standard relaxation for hitting set in system (A,C)(\mathcal{A},\mathcal{C}):

minimize∑p∈Axps.t.∑p∈Cxp≥1∀C∈C0≤xp≤1∀p∈A\begin{aligned} \text{minimize}\quad&\sum_{p\in\mathcal{A}} x_p\\ \text{s.t.}\quad&\sum_{p\in C} x_p \ge1 \qquad\forall C \in\mathcal{C}\\ &0 \le x_p \le1 \qquad\forall p \in\mathcal{A} \end{aligned}

Let τ∗(F)\tau^*(F) be the weight of the solution to the corresponding linear programming relaxation, also called the fractional piercing number. For a point set PP weighted in accordance with the solution to the LP, every convex set in C\mathcal{C} has weight at least 1, and thus a 1τ∗(F)\frac{1}{\tau^*(F)}-net gives a piercing set for C\mathcal{C}. Conversely, assigning weight 1ε∣P∣\frac{1}{\varepsilon|P|} to all points in PP yields a fractional solution to the linear programming relaxation for (Rd,Cε)(\mathbb{R}^d,\mathcal{C}_\varepsilon). This means that a lower bound on the size of an ε\varepsilon-net gives a lower bound for the integrality gap ratio τ(F)τ∗(F)\frac{\tau(F)}{\tau^*(F)}. Our improved lower bound yields:

Corollary 2. For every dimension d≥3d \ge3 there is a constant cdc_d such that for every sufficiently large rr, there exists a finite family F\mathcal{F} of convex sets in Rd\mathbb{R}^d such that:

τ∗(F)≤randτ(F)≥cdrγdwhereγd=12⌊8d+25−12⌋,\tau^*(F) \le r \qquad\text{and} \qquad\tau(F) \ge c_d r^{\gamma_d} \qquad\text{where} \qquad\gamma_d = \frac{1}{2}\left\lfloor\frac{\sqrt{8d+25}-1}{2}\right\rfloor,

giving an integrality gap of τ(F)τ∗(F)=Ω((τ∗(F))γd−1)\frac{\tau(F)}{\tau^*(F)} = \Omega((\tau^*(F))^{\gamma_d-1}).

Organization

We begin in § 3 by presenting two different lifts of the 2D grid into higher dimension. The first is a simple lifting construction into 4D which illustrates the key ideas in § 3.1. Using these ideas, we can strengthen the result by using a modified lift of a slightly shifted grid into just 3 dimensions in § 3.2. From there, we proceed to generalize the construction in § 4.

Lifting a 2D Grid for Lower Bounds

Lower Bound in Four Dimensions

In this section we describe a Ω(r3/2)\Omega(r^{3/2}) lower bound for 1r\frac{1}{r}-nets in 4D. Our starting point is the Elekes grid construction [11] of point-line incidences in the plane that shows the Szemerédi–Trotter incidence bound is tight [26]. Consider a grid of points P0P_0 and a set of lines LL defined as follows for an even integer q≥2q \ge2.

P0:=[q]×[2q2]andL={y=ax+b:a∈[q],b∈[q2]}P_0 := [q] \times[2q^2] \qquad\text{and} \qquad L = \{y = ax + b : a \in[q], b \in[q^2]\}

It is easy to verify that ∣P0∣=2q3|P_0| = 2q^3, ∣L∣=q3|L| = q^3, each line contains exactly qq points, and each point lies on at most qq lines.

We lift the point set to R4\mathbb{R}^4 using the injective map ψ:R2→R4\psi: \mathbb{R}^2 \to\mathbb{R}^4 defined by ψ(x,y)=(x,y,x2,xy)\psi(x,y) = (x,y,x^2,xy). Observe that for any line ℓ∈L\ell\in L, the lift ψ\psi maps the points of the line onto a quadratic curve, and thus all points of ϕ(ℓ∩P0)\phi(\ell\cap P_0) lie in convex position.

We will consider the points P:=ψ(P0)={ψ(p):p∈P0}P := \psi(P_0) = \{\psi(p) : p \in P_0\} and the following family of convex sets Cℓ\mathcal{C}_{\ell} in R4\mathbb{R}^4 each with at least q/2q/2 points on a line ℓ\ell.

Cℓ={C=conv⁡(ψ(C0)):C0 is a set of exactly q/2 points of ℓ∩P0}C=⋃ℓ∈LCℓ\mathcal{C}_{\ell} = \{C = \operatorname{conv}(\psi(C_0)) : C_0 \text{ is a set of exactly } q/2 \text{ points of } \ell\cap P_0\} \qquad \mathcal{C} = \bigcup_{\ell\in L} \mathcal{C}_{\ell}

Each set of C\mathcal{C} contains at least q/2q/2 points out of the 2q32q^3 total number of points. In the remainder of this section suppose XX is a weak 1r\frac{1}{r}-net with r=4q2r = 4q^2 for PP. Observe that XX must hit each set of C\mathcal{C}.

Consider an arbitrary z=(z1,z2,z3,z4)∈Xz = (z_1,z_2,z_3,z_4) \in X, that hits some set conv⁡(ψ(C0))∈Cℓ\operatorname{conv}(\psi(C_0)) \in\mathcal{C}_{\ell}, where C0C_0 contains exactly q/2q/2 points {(x1,y1),…,(xq/2,yq/2)}\{(x_1,y_1),\ldots,(x_{q/2},y_{q/2})\} of ℓ∈L\ell\in L. Let ℓ\ell be defined by the equation y=ax+by = ax + b. We show that either zz is a point of the form ψ(xi,yi)\psi(x_i,y_i), or zz can pierce sets only from the family Cℓ\mathcal{C}_{\ell}.

Since zz is in the convex hull, there must be some nonnegative coefficients λi\lambda_i where ∑i=1q/2λi=1\sum_{i=1}^{q/2} \lambda_i = 1 and that z=∑i=1q/2λiψ(xi,yi)z = \sum_{i=1}^{q/2} \lambda_i \psi(x_i,y_i). It holds that

z2=∑i=1q/2λiyi=∑i=1q/2λi(axi+b)=az1+b.(1)z_2 = \sum_{i=1}^{q/2} \lambda_i y_i = \sum_{i=1}^{q/2} \lambda_i(ax_i+b) = az_1+b. \tag*{(1)}

Furthermore, as yi=axi+by_i = ax_i+b for all ii,

z4=∑i=1q/2λixiyi=∑i=1q/2λi(axi2+bxi)=a∑i=1q/2λixi2+b∑i=1q/2λixi=az3+bz1.(2)z_4 = \sum_{i=1}^{q/2} \lambda_i x_i y_i = \sum_{i=1}^{q/2} \lambda_i(ax_i^2+bx_i) = a\sum_{i=1}^{q/2} \lambda_i x_i^2 + b\sum_{i=1}^{q/2} \lambda_i x_i = az_3+bz_1. \tag*{(2)}

Note that these two equations define relations on ziz_i that holds regardless of the choice of convex representations λi\lambda_i. Eliminate bb by subtracting z1z_1 times Equation (1) from Equation (2). This yields

z4−z1z2=a(z3−z12).z_4-z_1z_2=a(z_3-z_1^2).

Observe that if z3−z12≠0z_3-z_1^2 \ne0, we can uniquely recover aa from the coordinates of zz by dividing (z3−z12)(z_3-z_1^2) on both sides, and also uniquely recover bb from Equation (1). Otherwise, it remains to consider z3−z12=0z_3-z_1^2=0, where we have that

0=z3−z12=∑iλixi2−(∑iλixi)2=∑iλi(xi−z1)2.0=z_3-z_1^2=\sum_i\lambda_i x_i^2-\left(\sum_i\lambda_i x_i\right)^2=\sum_i\lambda_i(x_i-z_1)^2.

Thus every xix_i with λi>0\lambda_i>0 has xi=z1x_i=z_1. Since the points (xi,yi)(x_i,y_i) lie on a non-vertical line ℓ\ell, we conclude that zz is the lift of a single point so z∈Pz\in P.

Size of the weak net Now we can bound the size of the weak 1r\frac{1}{r}-net XX. To do so, we will replace points of XX by lifted grid points while preserving the sets of C\mathcal{C} that are pierced. Consider any point z∈X∖Pz\in X\setminus P. We have shown that zz can only pierce convex sets from Cℓ\mathcal{C}_{\ell} for at most one line ℓz∈L\ell_z\in L. Thus if we replace zz with the points Qz:={ψ(x):x∈P0∩ℓz}Q_z:=\{\psi(x):x\in P_0\cap\ell_z\}, any convex set of Cℓz\mathcal{C}_{\ell_z} that was pierced by zz is also pierced by QzQ_z. Define Q:=⋃z∈X∖PQzQ:=\bigcup_{z\in X\setminus P}Q_z. Now the set X′:=(X∩P)∪QX':=(X\cap P)\cup Q must contain a strong 12\frac{1}{2}-net for Pℓ:=ψ(ℓ∩P0)P_{\ell}:=\psi(\ell\cap P_0) for every ℓ∈L\ell\in L as X′X' pierces all sets of Cℓ\mathcal{C}_{\ell} that have exactly q/2q/2 points. By the same argument as in the introduction, such a strong net must have at least q/2+1q/2+1 points of PℓP_{\ell}. As a single point of X∩PX\cap P belongs to at most qq sets PℓP_{\ell}, and each QzQ_z has at most qq points and contributes to at most one line ℓz\ell_z,

q3⋅(q/2+1)≤∑ℓ∈L∣X∩Pℓ∣+∑z∈X∖P∣Qz∣≤q∣X∩P∣+q∣X∖P∣⇒∣X∣≥q3/2+q2.q^3\cdot(q/2+1)\le\sum_{\ell\in L}|X\cap P_{\ell}|+\sum_{z\in X\setminus P}|Q_z|\le q|X\cap P|+q|X\setminus P|\qquad\Rightarrow\qquad|X|\ge q^3/2+q^2.

This proves the following result.

Theorem 2. For every even integer q≥2q\ge2 there is a set P⊂R4P\subset\mathbb{R}^4 of 2q32q^3 points whose weak 14q2\frac{1}{4q^2}-nets have size at least q3/2+q2q^3/2+q^2. Consequently, f4(r)=Ω(r3/2)f_4(r)=\Omega(r^{3/2}).

Improved Lift to Three Dimensions

We use the quadratic lift ϕ:R2→R3\phi:\mathbb{R}^2\to\mathbb{R}^3 defined by ϕ(x,y)=(x2,xy,y2)\phi(x,y)=(x^2,xy,y^2). We will lift the same grid construction as before with a parameter q≥2q\ge2 (assumed to be even for convenience), but with a crucial difference. Before applying the lift, translate the entire grid upwards by τ=19q5\tau=\frac{1}{9q^5}. To be precise, we define the following:

P+τ={(a,b+τ):a∈[q], b∈[2q2]}andL+τ={y=ax+b+τ:a∈[q], b∈[q2]}.P^{+\tau}=\{(a,b+\tau):a\in[q],\ b\in[2q^2]\}\qquad\text{and}\qquad L^{+\tau}=\{y=ax+b+\tau:a\in[q],\ b\in[q^2]\}.

Define as before P=ϕ(P+τ)P=\phi(P^{+\tau}) and Cℓ\mathcal{C}_{\ell} as well as C\mathcal{C} as follows:

Cℓ:={conv⁡(ϕ(S)):S⊆P+τ∩ℓ, ∣S∣=q/2},C:=⋃ℓ∈L+τCℓ.\mathcal{C}_{\ell}:=\{\operatorname{conv}(\phi(S)):S\subseteq P^{+\tau}\cap\ell,\ |S|=q/2\},\qquad\mathcal{C}:=\bigcup_{\ell\in L^{+\tau}}\mathcal{C}_{\ell}.

Let XX be a weak 1r\frac{1}{r}-net for PP, and consider a point z=(z1,z2,z3)∈Xz=(z_1,z_2,z_3)\in X that hits the convex set of the lift of q/2q/2 points {(x1,y1),…,(xq/2,yq/2)}\{(x_1,y_1),\ldots,(x_{q/2},y_{q/2})\} of some line ℓ∈L+τ\ell\in L^{+\tau}. We now show that either zz is a point of PP, or that zz pierces sets of Cℓi\mathcal{C}_{\ell_i} for at most four distinct lines ℓ1,ℓ2,ℓ3,ℓ4∈L+τ\ell_1,\ell_2,\ell_3,\ell_4\in L^{+\tau}.

Suppose zz hits a set in Cℓ\mathcal{C}_{\ell} for ℓ∈L+τ\ell\in L^{+\tau} that is defined by y=ax+b+τy=ax+b+\tau for which we can write z=∑iλiϕ(xi,yi)z=\sum_i\lambda_i\phi(x_i,y_i) with (xi,yi)(x_i,y_i) on ℓ\ell, and λi>0\lambda_i>0 with ∑iλi=1\sum_i\lambda_i=1. Thus we can define a quadratic function that depends only on zz as follows:

Gz(t)=∑iλi(txi−yi)2=t2∑iλixi2−2t∑iλixiyi+∑iλiyi2=z1t2−2z2t+z3.G_z(t)=\sum_i\lambda_i(tx_i-y_i)^2=t^2\sum_i\lambda_i x_i^2-2t\sum_i\lambda_i x_i y_i+\sum_i\lambda_i y_i^2=z_1t^2-2z_2t+z_3.

Furthermore, evaluating tt at the slope of ℓ\ell yields

Gz(a)=∑iλi(axi−yi)2=(b+τ)2G_z(a)=\sum_i\lambda_i(ax_i-y_i)^2=(b+\tau)^2

Now we will use the following lemma about GzG_z that we will defer to later.

Lemma 1. If a real polynomial G(t)G(t) of degree two satisfies G(a)=(b+τ)2G(a) = (b + \tau)^2 for at least five distinct pairs (a,b)∈[q]×[q2](a,b) \in[q] \times[q^2], then G(t)=α(t−t0)2G(t) = \alpha(t - t_0)^2 for some α,t0∈R\alpha, t_0 \in\mathbb{R}.

Suppose that zz hits sets from at least five distinct line families. Then, Lemma 1 gives z1t2−2z2t+z3=Gz(t)=α(t−t0)2z_1t^2 - 2z_2t + z_3 = G_z(t) = \alpha(t - t_0)^2. Observe that z1=∑iλixi2>0z_1 = \sum_i \lambda_i x_i^2 > 0, we must have α>0\alpha> 0. Evaluating at t0t_0 gives

0=Gz(t0)=∑iλi(t0xi−yi)2.0 = G_z(t_0) = \sum_i \lambda_i(t_0x_i - y_i)^2.

This can only happen if t0xi=yit_0x_i = y_i for all ii with λi>0\lambda_i > 0.

Since also yi=axi+b+τy_i = ax_i + b + \tau, we obtain (t0−a)xi=b+τ>0(t_0-a)x_i = b + \tau> 0. Thus t0≠at_0 \ne a, and all represented points have the same xx-coordinate and hence the same yy-coordinate. Consequently, zz is the lift of a single grid point, so z∈Pz \in P.

Thus we have shown that either z∈Pz \in P or that zz can hit convex sets from at most four lines ℓ∈L+τ\ell\in L^{+\tau}. Recalling the prior argument, each point in X∩PX \cap P is a part of at most qq lines, and each point of X∖PX \setminus P can be replaced by qq points on 4 different lines. This gives

q3(q2+1)≤q∣X∩P∣+4q∣X∖P∣≤4q∣X∣⇒∣X∣≥q3/8+q2/4.q^3\left(\frac{q}{2} + 1\right) \le q|X \cap P| + 4q|X \setminus P| \le4q|X| \quad\Rightarrow\quad|X| \ge q^3/8 + q^2/4.

This proves the following 3D lower bound.

Theorem 3. For every even integer q≥2q \ge2, there is a set P⊂R3P \subset\mathbb{R}^3 of 2q32q^3 points whose weak 14q2\frac{1}{4q^2}-nets have size at least q3/8+q2/4q^3/8 + q^2/4. Consequently, f3(r)=Ω(r3/2)f_3(r) = \Omega(r^{3/2}).

It remains to prove Lemma 1, that GzG_z must either be a square of a linear polynomial or has at most four distinct positive integer solutions.

Proof (of Lemma 1): Consider five unique integer solutions G(ai)=(bi+τ)2G(a_i) = (b_i + \tau)^2 with ai∈[q]a_i \in[q] and bi∈[q2]b_i \in[q^2] for i∈[5]i \in[5]. Note that the slopes aia_i are distinct since bib_i is uniquely determined by aia_i. Consider if we instead interpolated at the first three solutions polynomials of degree at most two satisfying

R(ai)=bi,T(ai)=bi2,for i=1,2,3.R(a_i)=b_i,\qquad T(a_i)=b_i^2,\qquad\text{for }i=1,2,3.

Lagrange interpolation gives

R(t)=∑i=13bi∏j=1j≠i3t−ajai−ajandT(t)=∑i=13bi2∏j=1j≠i3t−ajai−aj.R(t)=\sum_{i=1}^{3}b_i\prod_{\substack{j=1\\j\ne i}}^{3}\frac{t-a_j}{a_i-a_j} \qquad\text{and}\qquad T(t)=\sum_{i=1}^{3}b_i^2\prod_{\substack{j=1\\j\ne i}}^{3}\frac{t-a_j}{a_i-a_j}.

Without loss of generality, we may assume that a1<a2<a3a_1<a_2<a_3. Observe that by setting N=(a2−a1)(a3−a1)(a3−a2)>0N=(a_2-a_1)(a_3-a_1)(a_3-a_2)>0, we can clear the denominators so NR(t)NR(t) and NT(t)NT(t) are polynomials with integer coefficients.

At these first three points, we have

G(ai)=(bi+τ)2=T(ai)+2τR(ai)+τ2G(a_i)=(b_i+\tau)^2=T(a_i)+2\tau R(a_i)+\tau^2

Since both GG and T+2τR+τ2T+2\tau R+\tau^2 have degree at most two and agree at three points, they are identical as polynomials, so G(t)=T(t)+2τR(t)+τ2G(t)=T(t)+2\tau R(t)+\tau^2. We next show that R(ai)=biR(a_i)=b_i for i=4,5i=4,5. For any solution (a,b)(a,b),

(b+τ)2=G(a)=T(a)+2τR(a)+τ2(b+\tau)^2=G(a)=T(a)+2\tau R(a)+\tau^2
b2+2τb=T(a)+2τR(a)b^2+2\tau b=T(a)+2\tau R(a)
N(b2−T(a))=2τN(R(a)−b)(3)N(b^2-T(a))=2\tau N(R(a)-b) \tag*{(3)}

The left side of Equation (3) is clearly integral because NT(a)NT(a) and Nb2Nb^2 are integers. On the right side, we can bound the absolute value of 2τN(R(a)−b)2\tau N(R(a)-b) for any a∈[q]a\in[q] and b∈[q2]b\in[q^2] by using ∣N∣≤q3|N|\le q^3 and ∣NR(a)∣≤3q5|NR(a)|\le3q^5.

2τ(∣NR(a)∣+∣Nb∣)≤2τ(3q5+q5)≤8q59q5<12\tau(|NR(a)|+|Nb|)\le2\tau(3q^5+q^5)\le\frac{8q^5}{9q^5}<1

Since the only integer with absolute value less than one is zero, we conclude that both sides of Equation (3) vanish for each solution (a,b)(a,b), so all five solutions satisfy R(a)=bR(a)=b. Thus G(t)−(R(t)+τ)2G(t)-(R(t)+\tau)^2 has five distinct roots a1,…,a5a_1,\ldots,a_5, but has degree at most four, so must be identically zero. This means G(t)=(R(t)+τ)2G(t)=(R(t)+\tau)^2. Since GG has degree two, RR must have degree one, giving the representation as desired. □

Remark Further analysis can show that every point z∉Pz\notin P can hit convex sets arising from at most 3 distinct lines. The bound of 4 suffices for our purposes, so we omit the lengthier analysis. See Figure 3 for a concrete example of 3 convex hulls with a common point.

Lifted points and intersecting triangles

Figure 3. On the left is a plot of the lifted points for q=6q = 6 and τ=1/69984\tau= 1/69984 along with three intersecting triangles arising from three distinct lines. These triangles intersect at a point zz. The dotted box on the left denotes the skewed and rescaled view on the right where it is more clear that the three triangles are intersecting at z=(24130+τ15,97712+17τ6,44195+298τ5+τ2)z = \left(\frac{241}{30} + \frac{\tau}{15}, \frac{977}{12} + \frac{17\tau}{6}, \frac{4419}{5} + \frac{298\tau}{5} + \tau^2\right).

Generalization to Higher Dimensions

In this section we give a higher dimensional generalization of our 3D lift. Fix an integer s≥1s\ge1, and an even integer q≥2q\ge2. Set Ds=(s2+5s)/2D_s=(s^2+5s)/2 and τ=19q5\tau=\frac{1}{9q^5} as before. We will construct a point set in RDs\mathbb{R}^{D_s} from the shifted grid in Rs+1\mathbb{R}^{s+1} that supports many rich hyperplanes. Define points p=(x1,…,xs,xs+1)p=(x_1,\ldots,x_s,x_{s+1}) in the shifted grid, with the shifted hyperplanes as below.

P0+τ:={(x1,…,xs,xs+1+τ):x∈[q]s, xs+1∈[(s+1)q2]}P_0^{+\tau}:=\{(x_1,\ldots,x_s,x_{s+1}+\tau):x\in[q]^s,\ x_{s+1}\in[(s+1)q^2]\}
H+τ={Ha,b:xs+1=a1x1+⋯+asxs+b+τ:a∈[q]s, b∈[q2]}\mathcal{H}^{+\tau}=\{H_{a,b}:x_{s+1}=a_1x_1+\cdots+a_sx_s+b+\tau:a\in[q]^s,\ b\in[q^2]\}

Observe that ∣P0+τ∣=(s+1)qs+2|P_0^{+\tau}|=(s+1)q^{s+2} and ∣H+τ∣=qs+2|\mathcal{H}^{+\tau}|=q^{s+2}. Let BH:=P0+τ∩HB_H:=P_0^{+\tau}\cap H for H∈H+τH\in\mathcal{H}^{+\tau}. Every choice of x∈[q]sx\in[q]^s gives one point of BHB_H, so ∣BH∣=qs|B_H|=q^s. We define the lift ϕs:Rs+1→RDs\phi_s:\mathbb{R}^{s+1}\to\mathbb{R}^{D_s} as follows:

ϕs(p):=(x1,…,xs−1,(xixj)1≤i≤j≤s+1)\phi_s(p):=(x_1,\ldots,x_{s-1},(x_ix_j)_{1\le i\le j\le s+1})

Note that we retain all quadratic coordinates and omit the xsx_s and xs+1x_{s+1} term in the lift. Define as before P+τ=ϕs(P0+τ)P^{+\tau}=\phi_s(P_0^{+\tau}) and CH\mathcal{C}_H to be the family of convex hulls of lifted points with exactly qs/2q^s/2 points on the hyperplane H∈H+τH\in\mathcal{H}^{+\tau}, and let C=⋃H∈H+τCH\mathcal{C}=\bigcup_{H\in\mathcal{H}^{+\tau}}\mathcal{C}_H. Every member of C\mathcal{C} contains at least qs/2q^s/2 of the (s+1)qs+2(s+1)q^{s+2} input points. Consequently, every weak 1/r1/r-net must hit every member of C\mathcal{C}, where r=2(s+1)q2r=2(s+1)q^2.

To generalize the counting argument of the three dimensional construction, we show that every point of a weak net can be replaced by O(qs)O(q^s) points of P+τP^{+\tau}. We defer the following proof to after the counting argument.

Lemma 2 (Replacement Set Lemma). For every point z∈RDsz\in\mathbb{R}^{D_s}, there exists a collection Qz,H⊆ϕs(BH)Q_{z,H}\subseteq\phi_s(B_H) for every H∈H+τH\in\mathcal{H}^{+\tau} such that zz pierces C∈CHC\in\mathcal{C}_H means that Qz,H∩C≠∅Q_{z,H}\cap C\ne\varnothing and ∑H∈H+τ∣Qz,H∣≤4qs\sum_{H\in\mathcal{H}^{+\tau}}|Q_{z,H}|\le4q^s.

Let XX be a weak 1/r1/r-net for P+τP^{+\tau} with r=2(s+1)q2r=2(s+1)q^2. For each hyperplane H∈H+τH\in\mathcal{H}^{+\tau}, define UH=⋃z∈XQz,H⊆ϕs(BH)U_H=\bigcup_{z\in X}Q_{z,H}\subseteq\phi_s(B_H). By Lemma 2, UHU_H is a strong 1/21/2-net for ϕs(BH)\phi_s(B_H). Since the points of ϕs(BH)\phi_s(B_H) are in convex position, any strong 1/21/2-net must have size at least qs/2+1q^s/2+1. Summing over all qs+2q^{s+2} hyperplanes of H+τ\mathcal{H}^{+\tau} yields:

qs+2(qs2+1)≤∑H∈H+τ∣UH∣≤∑H∈H+τ∑z∈X∣Qz,H∣≤4qs∣X∣⇒∣X∣≥qs+28+q24=Ω(qs+2)=Ω(r(s+2)/2).q^{s+2}\left(\frac{q^s}{2}+1\right)\le\sum_{H\in\mathcal{H}^{+\tau}}|U_H|\le\sum_{H\in\mathcal{H}^{+\tau}}\sum_{z\in X}|Q_{z,H}|\le4q^s|X|\quad\Rightarrow\quad|X|\ge\frac{q^{s+2}}{8}+\frac{q^2}{4}=\Omega(q^{s+2})=\Omega\left(r^{(s+2)/2}\right).

Thus we have proven the following theorem that is equivalent to Theorem 1.

Theorem 4. For every s≥1s\ge1, there are finite point sets in RDs\mathbb{R}^{D_s} with Ds=(s2+5s)/2D_s=(s^2+5s)/2 whose weak 1/r1/r-nets require Ω(r(s+2)/2)\Omega\left(r^{(s+2)/2}\right) points.

It remains to prove Lemma 2.

Proof (of Lemma 2): Call a set H∈H+τH\in\mathcal{H}^{+\tau} compatible with a point zz if z∈conv⁡(ϕs(BH))z\in\operatorname{conv}(\phi_s(B_H)). If no such hyperplane exists, the point is irrelevant and set Qz,H=∅Q_{z,H}=\varnothing for all hyperplanes HH. Henceforth we may assume at least one such HH exists for zz. Fix a representation of zz as the convex combination of lifted points p(i)p^{(i)} on H∩P0+τH\cap P_0^{+\tau}.

z=∑i=1mλiϕs(p(i)),p(i)=(p1(i),…,ps(i),ps+1(i)),∑iλi=1,λi>0z=\sum_{i=1}^{m}\lambda_i\phi_s(p^{(i)}),\qquad p^{(i)}=(p^{(i)}_1,\ldots,p^{(i)}_s,p^{(i)}_{s+1}),\qquad\sum_i\lambda_i=1,\qquad\lambda_i>0

For notational convenience, write the coordinates of zz as:

z=(z1,…,zs−1,(zi,j)1≤i≤j≤s+1)andzj,i=zi,j.z=(z_1,\ldots,z_{s-1},(z_{i,j})_{1\le i\le j\le s+1})\qquad\text{and}\qquad z_{j,i}=z_{i,j}.

Consider the subspace Fz:=span⁡{p(1),…,p(m)}F_z:=\operatorname{span}\{p^{(1)},\ldots,p^{(m)}\} and let k:=dim⁡Fz−1k:=\dim F_z-1. We claim that FzF_z does not depend on the choice of representation for zz, since for any vector u∈Rs+1u\in\mathbb{R}^{s+1}, we have that:

∑i=1mλi(u⋅p(i))2=∑j=1s+1∑k=1s+1ujuk∑i=1mλipj(i)pk(i)=∑j=1s+1∑k=1s+1ujukzj,k.\sum_{i=1}^{m}\lambda_i(u\cdot p^{(i)})^2=\sum_{j=1}^{s+1}\sum_{k=1}^{s+1}u_ju_k\sum_{i=1}^{m}\lambda_i p_j^{(i)}p_k^{(i)}=\sum_{j=1}^{s+1}\sum_{k=1}^{s+1}u_ju_kz_{j,k}.

Thus uu is orthogonal to every p(i)p^{(i)} and thus to FzF_z if and only if the left side is 0. This can be computed with the coordinates of uu and zz, and is thus independent of the choice of convex combination.

Replacement points We define the replacement points Qz,H:=ϕs(P0+τ∩Fz∩H)Q_{z,H}:=\phi_s(P_0^{+\tau}\cap F_z\cap H) for all HH where z∈conv⁡(ϕs(H∩P0+τ))z\in\operatorname{conv}(\phi_s(H\cap P_0^{+\tau})) and empty otherwise. The set Fz∩HF_z\cap H is a kk-dimensional flat as FzF_z contains the origin, but HH does not. It is easy to see that the number of grid points on a projected flat has size at most ∣Qz,H∣≤qk|Q_{z,H}|\le q^k, and that the number of hyperplanes that contain the kk-dimensional flat Fz∩HF_z\cap H is at most qs−kq^{s-k}. It suffices to show that there are at most four such flats Fz∩HF_z\cap H, which would imply that ∑H∈H+τ∣Qz,H∣≤4qk⋅qs−k=4qs\sum_{H\in\mathcal{H}^{+\tau}}|Q_{z,H}|\le4q^k\cdot q^{s-k}=4q^s.

Hyperplanes containing the flat Fix the hyperplane H=Ha,bH=H_{a,b} defined by xs+1=a1x1+⋯+asxs+b+τx_{s+1}=a_1x_1+\cdots+a_sx_s+b+\tau. We know that all points p(i)p^{(i)} for i∈[m]i\in[m] lie on HH. Inspecting the coordinates of zz for j∈[s−1]j\in[s-1] yields:

zj,s+1=∑i=1mλipj(i)ps+1(i)=∑i=1mλipj(i)(b+τ+∑k=1sakpk(i))=(b+τ)zj+∑k=1sakzj,k.(4)z_{j,s+1}=\sum_{i=1}^{m}\lambda_i p_j^{(i)}p_{s+1}^{(i)}=\sum_{i=1}^{m}\lambda_i p_j^{(i)}\left(b+\tau+\sum_{k=1}^{s}a_kp_k^{(i)}\right)=(b+\tau)z_j+\sum_{k=1}^{s}a_kz_{j,k}. \tag*{(4)}

Observe that if we treat bb and aka_k as variables and zz as fixed, we obtain s−1s-1 equations over s+1s+1 unknowns. Thus using Gaussian elimination setting additional free variables to 0, we can express every aka_k for k∈[s−1]k \in[s-1] as a degree at most one equation of (the variables) asa_s and bb. Any setting of the free variables yields equivalent affine forms and thus the same flat. Each pair (as,b)(a_s,b) determines the flat Fz∩HF_z \cap H, although different pairs may determine the same flat. Let a^k(t,h)\hat{a}_k(t,h) denote this affine function, and define a^s(t,h)=t\hat{a}_s(t,h)=t. Note that we can always write a^j(t,h)=a^j(t,0)+ηjh\hat{a}_j(t,h)=\hat{a}_j(t,0)+\eta_jh, where ηj\eta_j is the coefficient of hh.

For p∈Fzp \in F_z, membership in HH is equivalent to the following equation.

ps+1=∑j=1s−1(a^j(as,0)+(b+τ)ηj)pj+asps+b+τ=∑j=1sa^j(as,0)pj+(b+τ)(1+∑j=1s−1ηjpj)p_{s+1}=\sum_{j=1}^{s-1}\left(\hat{a}_j(a_s,0)+(b+\tau)\eta_j\right)p_j+a_sp_s+b+\tau=\sum_{j=1}^{s}\hat{a}_j(a_s,0)p_j+(b+\tau)\left(1+\sum_{j=1}^{s-1}\eta_jp_j\right)

Rearranging this equation yields:

ps+1−∑j=1sa^j(as,0)pj=(b+τ)(1+∑j=1s−1ηjpj).(5)p_{s+1}-\sum_{j=1}^{s}\hat{a}_j(a_s,0)p_j=(b+\tau)\left(1+\sum_{j=1}^{s-1}\eta_jp_j\right). \tag*{(5)}

For fixed pp and zz, the two sides depend on asa_s and bb respectively. The LHS motivates the following definition of a quadratic polynomial Gz(t)G_z(t):

Gz(t):=∑i=1mλi(ps+1(i)−∑j=1sa^j(t,0)pj(i))2=zs+1,s+1−2∑j=1sa^j(t,0)zj,s+1+∑j=1s∑ℓ=1sa^j(t,0)a^ℓ(t,0)zj,ℓ.\begin{aligned} G_z(t):=\sum_{i=1}^{m}\lambda_i\left(p_{s+1}^{(i)}-\sum_{j=1}^{s}\hat{a}_j(t,0)p_j^{(i)}\right)^2 \\ &=z_{s+1,s+1}-2\sum_{j=1}^{s}\hat{a}_j(t,0)z_{j,s+1}+\sum_{j=1}^{s}\sum_{\ell=1}^{s}\hat{a}_j(t,0)\hat{a}_\ell(t,0)z_{j,\ell}. \end{aligned}

By Equation (5), any valid pair (as,b)(a_s,b) satisfies:

Gz(as)=(b+τ)2∑i=1mλi(1+∑j=1s−1ηjpj(i))2⏟determined only by z.(6)G_z(a_s)=(b+\tau)^2\underbrace{\sum_{i=1}^{m}\lambda_i\left(1+\sum_{j=1}^{s-1}\eta_jp_j^{(i)}\right)^2}_{\text{determined only by }z}. \tag*{(6)}

For shorthand, define Δz\Delta_z to be the part that depends only on zz, so Gz(as)=Δz(b+τ)2G_z(a_s)=\Delta_z(b+\tau)^2.

Counting the flats By the definition of GzG_z as a sum of squares, Δz≥0\Delta_z \ge0.

Suppose that Δz=0\Delta_z=0, and fix a compatible hyperplane with last slope asa_s. Then

0=Gz(as)=∑iλi(ps+1(i)−∑j=1sa^j(as,0)pj(i))2.0=G_z(a_s)=\sum_i\lambda_i\left(p_{s+1}^{(i)}-\sum_{j=1}^{s}\hat{a}_j(a_s,0)p_j^{(i)}\right)^2.

Discarding zero weights, we may assume that every λi>0\lambda_i>0. Thus every represented point satisfies

ps+1(i)=∑j=1sa^j(as,0)pj(i).p_{s+1}^{(i)}=\sum_{j=1}^{s}\hat{a}_j(a_s,0)p_j^{(i)}.

Since this equation is homogeneous and linear in pp, it holds throughout FzF_z. Consequently the defining equation of every compatible hyperplane restricted to FzF_z reduces to 1+∑j<sηjpj=01+\sum_{j<s}\eta_jp_j=0. Thus all compatible hyperplanes determine the same flat in FzF_z.

We now consider when Δz>0\Delta_z > 0. We break into two cases. In the first case, consider if GzG_z is not a square of a degree one polynomial. A nonnegative quadratic that is not a square has no real root, so Δz≥0\Delta_z \ge0. Now we can apply Lemma 1 to Gz/ΔzG_z/\Delta_z, and obtain at most four distinct integer solution pairs (as,b)(a_s,b), and thus at most four distinct flats.

If GzG_z is constant, the vanishing t2t^2-coefficient in its expression as a sum of squares forces ps+1−∑j=1sa^j(t,0)pjp_{s+1}-\sum_{j=1}^{s}\hat{a}_j(t,0)p_j to be independent of tt, hence on its linear span FzF_z. Since Gz(as)=Δz(b+τ)2G_z(a_s)=\Delta_z(b+\tau)^2 also fixes b+τ>0b+\tau>0 when Δz>0\Delta_z>0, all compatible hyperplanes induce the same flat in FzF_z.

Otherwise, we can assume that GzG_z is nonconstant and thus a square so that Gz(t)=α(t−t0)2G_z(t)=\alpha(t-t_0)^2 for real values α,t0∈R\alpha,t_0\in\mathbb{R}. Since also Gz(as)=Δz(b+τ)2G_z(a_s)=\Delta_z(b+\tau)^2, the following ratio takes on at most two distinct values.

as−t0b+τ=±Δzα.\frac{a_s-t_0}{b+\tau}=\pm\sqrt{\frac{\Delta_z}{\alpha}}.

As Gz(t0)=0G_z(t_0)=0 and GzG_z is a sum of squares, it follows that for all p(i)p^{(i)}, the term t−t0t-t_0 is a factor of ps+1(i)−∑j=1sa^j(t,0)pjp_{s+1}^{(i)}-\sum_{j=1}^{s}\hat{a}_j(t,0)p_j. By linearity this also holds for all p∈Fzp\in F_z. Using the defining hyperplane equation of Equation (5), the LHS of the equation (treating asa_s as a variable) is a linear polynomial in asa_s with a root at t0t_0, thus can be rewritten as α′(as−t0)=β′(b+τ)\alpha'(a_s-t_0)=\beta'(b+\tau), where α′\alpha' and β′\beta' are constants that depend on zz and pp. Thus the hyperplane equation is invariant up to the value of as−t0b+τ\frac{a_s-t_0}{b+\tau}. Since this can take on at most two values, there are at most two distinct flats.

Over all cases we have shown that there are at most four distinct flats. Recalling that each flat contains qkq^k grid points, and is contained in at most qs−kq^{s-k} hyperplanes, we conclude that the number of replacement points is at most 4qs4q^s.

AI Acknowledgment

An initial proof of the lower bound result was obtained through discussions with ChatGPT-6 Astra. The authors subsequently verified its correctness, simplified the argument, and substantially revised the exposition. The authors take full responsibility for the results and proofs presented in this paper.

References

  1. [2][Afs13] Peyman Afshani. Improved pointer machine and I/O lower bounds for simplex range reporting and related problems. Int. J. Comput. Geom. Appl., 23(4-5):233–252, 2013. doi:10.1142/S0218195913600054.DOI
  2. [3][AK92] Noga Alon and Daniel J. Kleitman. Piercing convex sets and the Hadwiger-Debrunner (p,q)-problem. Adv. Math., 96(1):103–112, 1992. doi:10.1016/0001-8708(92)90052-M.DOI
  3. [4][AKMM02] Noga Alon, Gil Kalai, Jiří Matoušek, and Roy Meshulam. Transversal numbers for hypergraphs arising in geometry. Advances in Applied Mathematics, 29(1):79–101, 2002.DOI
  4. [5][BG95] H. Brönnimann and M. T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete & Computational Geometry, 14(4):463–479, 1995. doi:10.1007/BF02570718.DOI
  5. [6][BHK20] Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of data science. Cambridge University Press, 2020.DOI
  6. [7]Boris Bukh, Jiří Matoušek, and Gabriel Nivasch. Lower bounds for weak epsilon-nets and stair-convexity. In Proceedings of the 25th ACM Symposium on Computational Geometry, Aarhus, Denmark, 2009, pages 1–10. ACM, 2009. doi:10.1145/1542362.1542365.
  7. [8]Boris Bukh, Jiří Matoušek, and Gabriel Nivasch. Lower bounds for weak epsilon-nets and stair-convexity. Israel J. Math., 182(1):199–228, 2011. doi:10.1007/s11856-011-0029-1.DOI
  8. [9]József Balogh and József Solymosi. On the number of points in general position in the plane. Discrete Anal., 2018(16):1–20, 2018. doi:10.19086/da.4438.DOI
  9. [10]Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas J. Guibas, Micha Sharir, and Emo Welzl. Improved bounds on weak epsilon-nets for convex sets. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 495–504. ACM, 1993. doi:10.1145/167088.167222.DOI
  10. [11]György Elekes. Sums versus products in number theory, algebra and Erdős geometry. In Paul Erdős and His Mathematics, II, volume 11 of Bolyai Society Mathematical Studies, pages 241–290. János Bolyai Mathematical Society, Budapest, 2002.
  11. [12]Jeff Erickson. Space-time tradeoffs for emptiness queries. SIAM J. Comput., 29(6):1968–1996, 2000. doi:10.1137/S0097539798337212.DOI
  12. [13]Sathish Govindarajan and Gabriel Nivasch. A variant of the Hadwiger–Debrunner (p,q)-problem in the plane. Discret. Comput. Geom., 54(3):637–646, 2015. doi:10.1007/s00454-015-9723-9.DOI
  13. [14]H. Hadwiger and H. Debrunner. Über eine Variante zum Hellyschen Satz. Arch. Math., 8(4):309–313, 1957. doi:10.1007/BF01898794.DOI
  14. [15]David Haussler and Emo Welzl. Epsilon-nets and simplex range queries. In Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, Yorktown Heights, NY, USA, June 2-4, 1986, pages 61–71. ACM, 1986. doi:10.1145/10515.10522.DOI
  15. [16]David Haussler and Emo Welzl. Epsilon-nets and simplex range queries. Discret. Comput. Geom., 2:127–151, 1987. doi:10.1007/BF02187876.DOI
  16. [17]János Komlós, János Pach, and Gerhard J. Woeginger. Almost tight bounds for epsilon-nets. Discret. Comput. Geom., 7:163–173, 1992. doi:10.1007/BF02187833.
  17. [18]Chaya Keller and Shakhar Smorodinsky. A new lower bound on Hadwiger-Debrunner numbers in the plane. Israel J. Math., 244(2):649–680, 2021. doi:10.1007/s11856-021-2185-2.
  18. [19]Chaya Keller and Shakhar Smorodinsky. New quantitative bounds for the (p,q)-theorem for unions of convex sets. CoRR, abs/2608.13176, 2026. URL: https://arxiv.org/abs/2608.13176, arXiv: 2608.13176, doi:10.48550/arXiv.2608.13176.
  19. [20]Nabil H. Mustafa and Kasturi Varadarajan. Epsilon-approximations and epsilon-nets. In Handbook of Discrete and Computational Geometry, chapter 47, pages 1241–1267. CRC Press, 3 edition, 2017.arxiv.org/abs/1702.03676
  20. [21]Jiří Matoušek and Uli Wagner. New constructions of weak ε-nets. Discrete & Computational Geometry, 32(2):195–206, 2004. doi:10.1007/s00454-004-1116-4.DOI
  21. [22]Oliver Roche-Newton. A general-position problem for planar line arrangements. CoRR, abs/2607.25742, 2026. URL: https://arxiv.org/abs/2607.25742, arXiv:2607.25742, doi: 10.48550/arXiv.2607.25742.
  22. [23]Natan Rubin. An improved bound for weak epsilon-nets in the plane. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 224–235. IEEE Computer Society, 2018. doi:10.1109/FOCS.2018.00030.DOI
  23. [24]Natan Rubin. Stronger bounds for weak epsilon-nets in higher dimensions. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 989–1002. ACM, 2021. doi:10.1145/3406325.3451062.DOI
  24. [25]Natan Rubin. Stronger bounds for weak epsilon-nets in higher dimensions. CoRR, abs/2104.12654, 2021. URL: https://doi.org/10.48550/arXiv.2104.12654, arXiv:2104.12654, doi:10.48550/ARXIV.2104.12654.
  25. [26]Endre Szemerédi and William T. Trotter. Extremal problems in discrete geometry. Combinatorica, 3(3):381–392, 1983. doi:10.1007/BF02579194.DOI
  26. [27]Andrew Suk and Ji Zeng. On higher dimensional point sets in general position. Comb. Probab. Comput., 35(1):134–148, 2026. doi:10.1017/S0963548325100254.DOI
  27. [28]Roman Vershynin. High-dimensional probability. Cambridge Series in Statistical and Probabilistic Mathematics, 47, 2019.

Paper details

vlnc:W_agh3y8xb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents