WorksComputer Science
Strong Lower Bounds for Weak Epsilon-Nets
Abstract
Let be a finite point set in . A weak -net for with respect to convex sets is a finite set intersecting every convex set containing at least points of . 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 , we construct point sets for which every weak -net has size . More generally, for every fixed , we obtain a lower bound of , where . Consequently, no upper bound of the form can hold with an absolute constant which is independent of the dimension. Despite the recent progress on upper bounds, the strongest previous general lower bound remained , 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 -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 -nets in their seminal work on geometric range searching in the 1980s [15, 16]. Let be a family of subsets of , let be a finite nonempty point set, and let . A strong -net for with respect to is a set that pierces every range containing at least points of . A weak -net satisfies the same piercing requirement but allows the points of to lie anywhere in . We study weak -nets for convex ranges. We denote by the family of all convex sets containing at least points of .
Many families of convex ranges, such as halfspaces or balls in fixed dimension, admit strong -nets whose size is independent of . This follows from the classical -net theorem. Every finite range space of Vapnik–Chervonenkis (VC) dimension admits a strong -net of size , for [15, 16, 17]. This bound is optimal in general. For every fixed and sufficiently small , there are range spaces of VC dimension at most in which every strong -net has size [17]. Thus, bounded VC dimension guarantees strong -nets of size nearly linear in , and the logarithmic factor cannot be removed in general.
On the other hand, arbitrary convex ranges exhibit a fundamentally different situation. In every dimension , the family of all convex sets has unbounded VC dimension. For instance, consider a set of points in convex position; then for every subset . Consequently, any set with at most points misses the convex hull of , which contains at least input points; see Figure 1. Every strong -net for such a configuration therefore requires at least points. For any fixed , this rules out a bound independent of .

Figure 1. For points in convex position, any candidate strong -net with misses the heavy convex set .
Allowing net points outside can dramatically reduce the number of points required, even in the plane. Let consist of the vertices of a regular -gon centered at the origin, where is even, and set . Every convex set containing at least vertices contains an antipodal pair and hence the origin. Thus, the origin alone forms a weak -net, whereas the preceding argument shows that every strong -net contains at least points; see Figure 2.

Figure 2. For the vertices of a regular even -gon and , the origin alone forms a weak -net, while every strong -net requires at least points.
Throughout the paper, we write and discuss weak -nets. For a finite nonempty set , let denote the minimum cardinality of a weak -net for with respect to all convex ranges in . We define the corresponding worst-case size by
A fundamental theorem of Alon, Bárány, Füredi, and Kleitman shows that is bounded by a polynomial in for every fixed dimension [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 -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 , normalization makes every set -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 -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 -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 [ABFK92]. In higher dimensions, Chazelle, Edelsbrunner, Grigni, Guibas, Sharir, and Welzl obtained
where depends only on , 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 for every fixed [23]. In a subsequent work [24] at STOC 2021, Rubin improved the exponent below in every fixed dimension . See Table 1 for the precise exponents he attained.
Table 1. Table of current best lower and upper bounds for . New results in this paper are written in red. The existing upper bounds4 hold for an arbitrary value .
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
for every fixed , 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 . Could weak nets always have size in every fixed dimension, or does some fixed dimension require polynomially superlinear size? Despite the upper bounds having exponents that grow with , no lower bound of the form , for a fixed , was known in any fixed dimension.
Our results
Theorem 1. For every integer , define
There exist constants and , such that for every there is a point set for which every weak -net with respect to convex sets has at least points. Consequently .
The following table illustrates the dimensions required to obtain the first few distinct values of .
The starting point for our theorem is to apply a quadratic lift to a configuration of points on a 2D grid following Elekes’ [11] construction with many point-line incidences. Define . For every 2D line , the lifted points are in convex position. We examine the 2D -rich lines that contain many 2D points of , and 4D convex hulls of point sets that contain exactly points of . 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 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 in 4D.
We can reduce the dimensionality of the lower bound to 3D by slightly shifting the grid before performing a modified lift . 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 dimensional grid to 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 to the vector 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.
-Theorem and Hadwiger-Debrunner numbers
A family of sets satisfies the -property if every among any sets in , there are sets which share a non-empty intersection. It was posed by Hadwiger and Debrunner [14] whether every family of convex sets in with satisfying the -property can be pierced by a set of points whose size depends only on , , and . Alon and Kleitman [3] prove this in their celebrated -theorem. This value is known as the Hadwiger-Debrunner number and is denoted by . To be precise the Hadwiger–Debrunner number is the least integer such that every finite family of nonempty convex sets in , with at least members and satisfying the -property, can be pierced by at most 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 . In higher dimensions, Keller and Smorodinsky [19] utilized the higher dimensional general position constructions of Suk and Zeng [27] that show that for , that for any .
Lower bounds for weak -nets transfer directly to Hadwiger–Debrunner numbers [13, 18]. Indeed, given a finite point set , let be the family of convex hulls of subsets of containing at least points. Among any members of , a simple counting argument shows that there must be a point of contained in at least of them. Thus this family satisfies the -property, while every piercing set is a weak -net with respect to all convex sets. Consequently, so a lower bound of the form implies a lower bound of . The weak net lower bound due to Bukh, Matoušek, and Nivasch [8] results in a lower bound of . A corollary of our result is a new lower bound for .
Corollary 1. For any dimension , and all ,
We observe that this leads to two refinements of existing lower bounds on . The first is that this yields a lower bound where the exponent increases beyond 2 provided . The second is that even if for some constant , in sufficiently high dimension , the quantity is superlinear in .
Approximating Minimum Piercing Set
For a set system , the minimum hitting set is the minimum cardinality set such that for every , . In this sense, a strong -net is a hitting set for the set system and a weak -net is a hitting set for . Let be the cardinality of the minimum hitting set of . When , we will use the term minimum piercing set.
On the positive side, the existence of -sized strong -nets for a given set system implies a polynomial time algorithm which returns a hitting set of size , 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 are modified when the calling to the -net construction fails to return a valid hitting set. In the case of approximating a minimum piercing set, all points in are valid elements to use for hitting and the sets to be hit are the input convex regions . To make the universe finite, assign a representative point from each cell in the arrangement induced by . Weak -nets in therefore correspond to strong -nets in the set system . Thus, Rubin’s [25] upper bound implies polynomial time approximation algorithms that are at worst polynomial in the optimal solution, namely for fixed .
The existence of weak -nets for with respect to is also intimately related to the linear programming relaxation of minimum piercing set. Here, we use the standard relaxation for hitting set in system :
Let be the weight of the solution to the corresponding linear programming relaxation, also called the fractional piercing number. For a point set weighted in accordance with the solution to the LP, every convex set in has weight at least 1, and thus a -net gives a piercing set for . Conversely, assigning weight to all points in yields a fractional solution to the linear programming relaxation for . This means that a lower bound on the size of an -net gives a lower bound for the integrality gap ratio . Our improved lower bound yields:
Corollary 2. For every dimension there is a constant such that for every sufficiently large , there exists a finite family of convex sets in such that:
giving an integrality gap of .
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 lower bound for -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 and a set of lines defined as follows for an even integer .
It is easy to verify that , , each line contains exactly points, and each point lies on at most lines.
We lift the point set to using the injective map defined by . Observe that for any line , the lift maps the points of the line onto a quadratic curve, and thus all points of lie in convex position.
We will consider the points and the following family of convex sets in each with at least points on a line .
Each set of contains at least points out of the total number of points. In the remainder of this section suppose is a weak -net with for . Observe that must hit each set of .
Consider an arbitrary , that hits some set , where contains exactly points of . Let be defined by the equation . We show that either is a point of the form , or can pierce sets only from the family .
Since is in the convex hull, there must be some nonnegative coefficients where and that . It holds that
Furthermore, as for all ,
Note that these two equations define relations on that holds regardless of the choice of convex representations . Eliminate by subtracting times Equation (1) from Equation (2). This yields
Observe that if , we can uniquely recover from the coordinates of by dividing on both sides, and also uniquely recover from Equation (1). Otherwise, it remains to consider , where we have that
Thus every with has . Since the points lie on a non-vertical line , we conclude that is the lift of a single point so .
Size of the weak net Now we can bound the size of the weak -net . To do so, we will replace points of by lifted grid points while preserving the sets of that are pierced. Consider any point . We have shown that can only pierce convex sets from for at most one line . Thus if we replace with the points , any convex set of that was pierced by is also pierced by . Define . Now the set must contain a strong -net for for every as pierces all sets of that have exactly points. By the same argument as in the introduction, such a strong net must have at least points of . As a single point of belongs to at most sets , and each has at most points and contributes to at most one line ,
This proves the following result.
Theorem 2. For every even integer there is a set of points whose weak -nets have size at least . Consequently, .
Improved Lift to Three Dimensions
We use the quadratic lift defined by . We will lift the same grid construction as before with a parameter (assumed to be even for convenience), but with a crucial difference. Before applying the lift, translate the entire grid upwards by . To be precise, we define the following:
Define as before and as well as as follows:
Let be a weak -net for , and consider a point that hits the convex set of the lift of points of some line . We now show that either is a point of , or that pierces sets of for at most four distinct lines .
Suppose hits a set in for that is defined by for which we can write with on , and with . Thus we can define a quadratic function that depends only on as follows:
Furthermore, evaluating at the slope of yields
Now we will use the following lemma about that we will defer to later.
Lemma 1. If a real polynomial of degree two satisfies for at least five distinct pairs , then for some .
Suppose that hits sets from at least five distinct line families. Then, Lemma 1 gives . Observe that , we must have . Evaluating at gives
This can only happen if for all with .
Since also , we obtain . Thus , and all represented points have the same -coordinate and hence the same -coordinate. Consequently, is the lift of a single grid point, so .
Thus we have shown that either or that can hit convex sets from at most four lines . Recalling the prior argument, each point in is a part of at most lines, and each point of can be replaced by points on 4 different lines. This gives
This proves the following 3D lower bound.
Theorem 3. For every even integer , there is a set of points whose weak -nets have size at least . Consequently, .
It remains to prove Lemma 1, that 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 with and for . Note that the slopes are distinct since is uniquely determined by . Consider if we instead interpolated at the first three solutions polynomials of degree at most two satisfying
Lagrange interpolation gives
Without loss of generality, we may assume that . Observe that by setting , we can clear the denominators so and are polynomials with integer coefficients.
At these first three points, we have
Since both and have degree at most two and agree at three points, they are identical as polynomials, so . We next show that for . For any solution ,
The left side of Equation (3) is clearly integral because and are integers. On the right side, we can bound the absolute value of for any and by using and .
Since the only integer with absolute value less than one is zero, we conclude that both sides of Equation (3) vanish for each solution , so all five solutions satisfy . Thus has five distinct roots , but has degree at most four, so must be identically zero. This means . Since has degree two, must have degree one, giving the representation as desired. □
Remark Further analysis can show that every point 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.

Figure 3. On the left is a plot of the lifted points for and along with three intersecting triangles arising from three distinct lines. These triangles intersect at a point . 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 .
Generalization to Higher Dimensions
In this section we give a higher dimensional generalization of our 3D lift. Fix an integer , and an even integer . Set and as before. We will construct a point set in from the shifted grid in that supports many rich hyperplanes. Define points in the shifted grid, with the shifted hyperplanes as below.
Observe that and . Let for . Every choice of gives one point of , so . We define the lift as follows:
Note that we retain all quadratic coordinates and omit the and term in the lift. Define as before and to be the family of convex hulls of lifted points with exactly points on the hyperplane , and let . Every member of contains at least of the input points. Consequently, every weak -net must hit every member of , where .
To generalize the counting argument of the three dimensional construction, we show that every point of a weak net can be replaced by points of . We defer the following proof to after the counting argument.
Lemma 2 (Replacement Set Lemma). For every point , there exists a collection for every such that pierces means that and .
Let be a weak -net for with . For each hyperplane , define . By Lemma 2, is a strong -net for . Since the points of are in convex position, any strong -net must have size at least . Summing over all hyperplanes of yields:
Thus we have proven the following theorem that is equivalent to Theorem 1.
Theorem 4. For every , there are finite point sets in with whose weak -nets require points.
It remains to prove Lemma 2.
Proof (of Lemma 2): Call a set compatible with a point if . If no such hyperplane exists, the point is irrelevant and set for all hyperplanes . Henceforth we may assume at least one such exists for . Fix a representation of as the convex combination of lifted points on .
For notational convenience, write the coordinates of as:
Consider the subspace and let . We claim that does not depend on the choice of representation for , since for any vector , we have that:
Thus is orthogonal to every and thus to if and only if the left side is 0. This can be computed with the coordinates of and , and is thus independent of the choice of convex combination.
Replacement points We define the replacement points for all where and empty otherwise. The set is a -dimensional flat as contains the origin, but does not. It is easy to see that the number of grid points on a projected flat has size at most , and that the number of hyperplanes that contain the -dimensional flat is at most . It suffices to show that there are at most four such flats , which would imply that .
Hyperplanes containing the flat Fix the hyperplane defined by . We know that all points for lie on . Inspecting the coordinates of for yields:
Observe that if we treat and as variables and as fixed, we obtain equations over unknowns. Thus using Gaussian elimination setting additional free variables to 0, we can express every for as a degree at most one equation of (the variables) and . Any setting of the free variables yields equivalent affine forms and thus the same flat. Each pair determines the flat , although different pairs may determine the same flat. Let denote this affine function, and define . Note that we can always write , where is the coefficient of .
For , membership in is equivalent to the following equation.
Rearranging this equation yields:
For fixed and , the two sides depend on and respectively. The LHS motivates the following definition of a quadratic polynomial :
By Equation (5), any valid pair satisfies:
For shorthand, define to be the part that depends only on , so .
Counting the flats By the definition of as a sum of squares, .
Suppose that , and fix a compatible hyperplane with last slope . Then
Discarding zero weights, we may assume that every . Thus every represented point satisfies
Since this equation is homogeneous and linear in , it holds throughout . Consequently the defining equation of every compatible hyperplane restricted to reduces to . Thus all compatible hyperplanes determine the same flat in .
We now consider when . We break into two cases. In the first case, consider if is not a square of a degree one polynomial. A nonnegative quadratic that is not a square has no real root, so . Now we can apply Lemma 1 to , and obtain at most four distinct integer solution pairs , and thus at most four distinct flats.
If is constant, the vanishing -coefficient in its expression as a sum of squares forces to be independent of , hence on its linear span . Since also fixes when , all compatible hyperplanes induce the same flat in .
Otherwise, we can assume that is nonconstant and thus a square so that for real values . Since also , the following ratio takes on at most two distinct values.
As and is a sum of squares, it follows that for all , the term is a factor of . By linearity this also holds for all . Using the defining hyperplane equation of Equation (5), the LHS of the equation (treating as a variable) is a linear polynomial in with a root at , thus can be rewritten as , where and are constants that depend on and . Thus the hyperplane equation is invariant up to the value of . 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 grid points, and is contained in at most hyperplanes, we conclude that the number of replacement points is at most .
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
- [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
- [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
- [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
- [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
- [6][BHK20] Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of data science. Cambridge University Press, 2020.DOI
- [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.
- [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
- [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
- [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
- [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.
- [12]Jeff Erickson. Space-time tradeoffs for emptiness queries. SIAM J. Comput., 29(6):1968–1996, 2000. doi:10.1137/S0097539798337212.DOI
- [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
- [14]H. Hadwiger and H. Debrunner. Über eine Variante zum Hellyschen Satz. Arch. Math., 8(4):309–313, 1957. doi:10.1007/BF01898794.DOI
- [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
- [16]David Haussler and Emo Welzl. Epsilon-nets and simplex range queries. Discret. Comput. Geom., 2:127–151, 1987. doi:10.1007/BF02187876.DOI
- [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.
- [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.
- [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.
- [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
- [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
- [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.
- [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
- [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
- [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.
- [26]Endre Szemerédi and William T. Trotter. Extremal problems in discrete geometry. Combinatorica, 3(3):381–392, 1983. doi:10.1007/BF02579194.DOI
- [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
- [28]Roman Vershynin. High-dimensional probability. Cambridge Series in Statistical and Probabilistic Mathematics, 47, 2019.