CS Paper Radar

Strong Lower Bounds for Weak Epsilon-Nets

Sujoy Bhore, Reilly Browne, Da Wei Zheng

cs.CG ·submitted 2026-10-29 21:06 UTC · v3
theory

Abstract

Let $P$ be a finite point set in $\mathbb{R}^d$. A weak $\varepsilon$-net for $P$ with respect to convex sets is a finite set $X\subset\mathbb{R}^d$ intersecting every convex set containing at least $\varepsilon|P|$ points of $P$. 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 $\mathbb{R}^3$, we construct point sets for which every weak $\varepsilon$-net has size $Ω(\varepsilon^{-3/2})$. More generally, for every fixed $d\ge3$, we obtain a lower bound of $Ω_d(\varepsilon^{-γ_d})$, where $γ_d=\sqrt{d/2}+O(1)$. Consequently, no upper bound of the form $O_d(\varepsilon^{-C})$ can hold with an absolute constant $C$ which is independent of the dimension. Despite the recent progress on upper bounds, the strongest previous general lower bound remained $Ω_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.

Closest papers

Nearest neighbours by meaning across the whole index.

A Linear Lower Bound for Convex Body Chasing in Every Norm

cs.DS cs.CGmath.MG ·2026-10-23 ·Nicolas Christianson
theory similarity 0.64
Abstract · Updates the previous version to extend the lower bound to all norms

We establish an $Ω(d)$ lower bound on the competitive ratio of convex body chasing in $\mathbb{R}^d$ with movement costs measured in any norm. Previously, the best known lower bound valid across all norms was $Ω(d^{1/6})$, established by Papazov (2023); stronger lower bounds were known for $\ell_p$ norms, where Bubeck, Klartag, Lee, Li, and Sellke (2019) had established a lower bound of $Ω(\max\{\sqrt{d}, d^{1-1/p}\})$. In particular, a linear lower bound was known only for the $\ell_\infty$ norm, realized by the standard construction of chasing faces of a hypercube. Our lower bound strictly improves on the prior universal and $\ell_p$ lower bounds for $p < \infty$ and shows that the functional Steiner point algorithm of Sellke (2023) - which has competitive ratio $O(d)$ - is asymptotically optimal for every norm. Our approach is based on the recursive construction of Bubeck, Coester, and Rabani (2023) for metrical service systems, which gives a lower bound of $Ω(r^2)$ for requests of size $O(r)$. We show that requests in their construction, each comprising a set of discrete points in a graph metric, can be mapped to the vertices of convex requests in a $(2r+1)$-dimensional $\ell_p$ vector space while approximately preserving movement costs up to a factor of $O(r)$; the general result then follows via Milman's (1985) quotient-of-a-subspace theorem.

0.29

New Quantitative Bounds for the $(p,q)$-Theorem for Unions of Convex Sets

cs.CG math.CO ·2026-08-13 ·Chaya Keller, Shakhar Smorodinsky
theory similarity 0.64
Abstract · 21 pages

A set in $\mathbb{R}^d$ is $s$-convex if it is the union of at most $s$ convex sets. A family $F$ satisfies the $(p,q)$ property if among any $p$ sets in $F$, some $q$ intersect. Let $\mathrm{HD}_d^{(s)}(p,q)$ be the minimum number of points needed to pierce a finite family of $s$-convex sets that satisfies the $(p,q)$-property. Alon and Kalai (1995) proved that $\mathrm{HD}_d^{(s)}(p,q)$ exists for any $p \geq q \geq d+1$ and any $s \geq 1$, but the quantitative bounds they obtained are very loose. We present several improved upper and lower bounds, for a general $d$ and for $s$-intervals of the line (i.e., $\mathrm{HD}_1^{(s)}(p,q)$). In particular, we prove the following: (i) For every $d\ge2$, $s \geq 1$ and $δ>0$, if $p>q$ and $q\ge C_d\log(e sp)$, then $\mathrm{HD}_d^{(s)}(p,q) \le p-q+1 + O_{d,δ}((s \cdot \tfrac{p}{q} \cdot \log \tfrac{esp}{q})^{ρ_d+δ}),$ where $ρ_d<d$ is the exponent in the weak epsilon-net theorem of Rubin (2022). (ii) For $s \geq 1$, $p \geq q \geq 2$ and $q\ge C_0s\log(2s)\log(ep)$, $p-q+s \leq \mathrm{HD}_1^{(s)}(p,q) \leq p-q+2s+1$. This result provides the first near-tight estimate for $\mathrm{HD}_1^{(s)}(p,q)$ for $q>2$. (iii) For any fixed $s$, there are an integer $κ_s\in\{s,\ldots,2s\}$ and constants $C_s,p_s>0$ such that, whenever $p\ge p_s$ and $q\ge C_s\log(ep)$, $ \mathrm{HD}_1^{(s)}(p,q)\in\{p-q+κ_s,\;p-q+κ_s+1\}. $ Interestingly, this two-value concentration result holds, although the exact value of the threshold remains unknown. (iv) For any $s \geq 1$, $\mathrm{HD}_3^{(s)}(p,4) \geq sp^{2-o(1)}$. Already for families of convex sets, this significantly improves the best known lower bound on $\mathrm{HD}_d^{(1)}(p,d+1)$, for all $d \geq 3$.

0.38

Approximating the Euclidean Ball by Polytopes: Surprising Rates in High Dimensions

cs.CG math.MGcs.LGmath.PR ·2026-10-26 ·Yegor Gorodzha, Steven Hoehner, Gil Kur
theory similarity 0.64
Abstract · 71 pages, 1 figure, 1 table. v2: exposition and references revised for a broader audience

We provide sharp estimates on the number of vertices needed to approximate the Euclidean unit ball $B_d\subset\mathbb R^d$ with relative symmetric-difference volume error at most $\varepsilon\in(0,1)$. We show that the minimum vertex budget $N_\varepsilon(d)$ satisfies $$\log N_\varepsilon(d)\asymp d\log\left(1+\frac1{\varepsilon\sqrt d}\right).$$ In particular, $\exp(O(\sqrt d/\varepsilon))$ vertices suffice for every $\varepsilon\in(0,1)$ and all sufficiently large $d$. We also prove that achieving a fixed error $\varepsilon\in(0,1)$ requires at least $Ω\bigl((\tfrac{1+\varepsilon}{2\sqrt\varepsilon})^{d-1}\bigr)$ facets, an exponential number in $d$. We extend our vertex approximation result to Gaussian symmetric-difference error, and give a positive answer to the question of De, Nadimpalli, and Servedio about subexponential vertex complexity for approximating Euclidean balls. We also disprove a Macbeath-type extremality principle for unrestricted vertex approximation. Whereas the ball uniformly maximizes the inscribed approximation error among all convex bodies (Macbeath, 1951), we show that approximating the hypercube $[-1,1]^d$ to relative error $\varepsilon$, with $δ:=1-\varepsilon$, requires $N\ge\fracδ{2}\exp(Ω(δ^2d/\log^2(2/δ)))$ vertices whenever $d\ge16\log(2/δ)$. Thus, when $d$ is large, the cube is harder to approximate than the ball in this sense. Finally, we determine the sharp dimensional order of the classical Laguerre-Delone triangulation number, showing that $\mathrm{ldel}_{d-1}=Θ(d^{-1/2})$ as $d\to\infty$. This improves both the upper bound of Ludwig, Schütt, and Werner and the lower bound of Böröczky by a factor of order $\sqrt d$. By classical asymptotic approximation theorems (Ludwig, 1999), this improvement applies to every convex body in $\mathbb R^d$ with $C^2$ boundary and positive Gaussian curvature.

0.34

The Sharp Dimension Bound in the Johnson--Lindenstrauss Lemma

cs.CG cs.DSmath.MGmath.PR ·2026-08-13 ·Vishesh Jain
theory similarity 0.62
Abstract · 13 pages; comments welcome!

The Johnson--Lindenstrauss lemma asserts that every set of $n$ points in $d$-dimensional Euclidean space embeds into $O(\varepsilon^{-2}\log n)$-dimensional Euclidean space with distortion at most $1+\varepsilon$. Larsen and Nelson conjectured that the optimal target dimension throughout the full range of the parameters $n,d, \varepsilon$ is \[ Θ\left(\min\left\{d,n-1,\frac{\log(2+\varepsilon^2n)}{\varepsilon^2}\right\}\right). \] We resolve this conjecture in the affirmative. In fact, we prove the stronger statement that the upper bound is attained by a linear map. The matching lower bound, due to Larsen--Nelson and Alon--Klartag, holds even for nonlinear embeddings.

0.10

Optimal Coresets for Hyperbolic Farthest-Point Queries via Ideal-Boundary Envelopes

cs.CG ·2026-10-01 ·Eunku Park
theory similarity 0.61
Abstract

We study coresets for farthest-point queries in hyperbolic space. Given a nonempty finite set $P \subset \mathbb{H}^D$ and $0<\varepsilon \le 1$, we seek a coreset $P_{\varepsilon} \subseteq P$ whose farthest distance from every query point underestimates that of $P$ by at most an additive $\varepsilon$ and retains at least a $1-\varepsilon$ fraction of it. For every fixed $D \ge 2$, we prove that the optimal worst-case coreset size is $Θ\bigl(\varepsilon^{-(D-1)/2}\bigr)$. Our main geometric ingredient is an exact reduction from hyperbolic queries to an upper envelope on the ideal boundary. In the hyperboloid model, each input point induces a positive boundary-score function whose logarithm gives its asymptotic distance offset along geodesic rays. We define the \emph{ideal-boundary envelope} as the pointwise maximum of these functions and prove that the supremum additive loss over all queries equals the maximum logarithmic gap between the input and coreset envelopes. For the upper bound, we move the minimum-enclosing-ball center to the origin and normalize the spatial coordinates, obtaining a bounded Euclidean point set whose boundary envelope is bounded away from zero. A standard Euclidean kernel then approximates all directional score maxima simultaneously, and the structure theorem yields both guarantees. For the lower bound, a spherical packing on a fixed-radius hyperbolic sphere, together with antipodal queries and the hyperbolic cosine law, makes every input point indispensable, matching the upper bound even for either guarantee separately.

0.37

Separating Measures by Hyperplanes

cs.CG math.MG ·2026-11-06 ·José Correa, Svenja M. Griesbach, Elfarouk Harb, Felix Hommelsheim, Reda Jlibene +2 more
theory similarity 0.60
Abstract · 58 pages, 5 figures

Given red and blue points in $\mathbb{R}^d$, connect every red point to every blue point and weigh each segment by its length under a fixed norm. What fraction of the total weight can always be captured by a single affine hyperplane separating the segments' endpoints? We study this question for finite point configurations in affine general position and, more generally, for pairs of probability measures. For dimension one, we show that choosing the best of three thresholds determined by the means of the two distributions captures at least one third of the total red-blue distance. We also give a matching upper bound. Embedding the line construction to higher dimensions shows that the guarantee of $1/3$ cannot be improved for arbitrary measures. Thus, we pivot to the family of measures whose atoms are in affine general position and whose non-atomic part places zero mass on all hyperplanes. Crucially, we establish that the worst-case guarantee is identical for finite configurations in affine general position and several natural classes of probability measures, thereby unifying the discrete and continuous formulations of the problem. For this family of measures and for higher dimensions, we extend our guarantee of $1/3$ for all norms. Our proofs combine the ham-sandwich theorem with a novel coupling argument and, in the planar case, an integral representation of norms. We also show that the optimal guarantee improves as the dimension grows, giving a lower bound of $1/2-\operatorname{O}\left(1/\sqrt{d}\right)$ as well as an asymptotically matching upper bound of $1/2$ for every $d$. For the Euclidean distance, we refine the lower bounds to $8/(8+5π)$ and $1/2-\operatorname{O}\left(1/d\right)$ and, for $d=2$, the upper bound to $5/11$. We also derive dimension-dependent guarantees for finite point configurations, including perfect separation of $n$ points of each color when $d\geq2n-1$.

0.27

Helly-Type Theorems for Splitting Point Sets

cs.CG math.COcs.DM ·2026-09-02 ·Lidor Portal, Natan Rubin
top venue similarity 0.60
Abstract · A preliminary version appeared in the Proceeding of SODA 2026

Let $0 < α\leq 1/2$. We say that a finite point set $P$ in $\mathbb{R}^d$ is $α$-split by a hyperplane $h$ if each of the closed half-spaces determined by $h$, contains at least $α|P|$ of the points of $P$. We further say $P$ is $α$-split by a $k$-dimensional flat $τ$ if $P$ is $α$-split by any hyperplane through $τ$. In the standard notation (which coincides with Tukey depth for $k= 0$), the $k$-flat $τ$ has depth $α$ with respect to $P$. We establish interesting Helly-type theorems for splitting families of finite point sets in $\mathbb{R}^d$. Unlike the classical sufficient Helly-type criteria for transversals to families of compact convex sets, which exist only for point and hyperplanes, our results extend to splitting families of point sets by collections of $k$-flats of arbitrary dimensionality $ 0 \leq k \leq d-1$.

0.40

Containment Problems in Convex Sets

cs.CG cs.DMmath.CO ·2026-11-06 ·Prosenjit Bose, Bobby Miraftab, Tyler Tuttle
theory similarity 0.59
Abstract

Let $P$ be a set of $n$ points in the plane, and let $C$ be a compact, convex subset of the plane that contains the origin in its interior. We study the problem of finding two points $p$ and $q$ of $P$ with the property that any homothet of $C$ that contains $p$ and $q$ must contain at least a constant fraction of the points of $P$. We give proofs for several cases. When $C$ is strictly convex we achieve a fraction of $1/5$, and when $C$ is a general convex region we achieve a fraction of $1/6e$. We show how the ideas of this second bound can be used to prove a lower bound for a version of the problem in $\mathbb{R}^d$ when $C$ is a $d$-ball. We also consider a few special cases. When $C$ is a triangle we get a lower bound of $1/12$, and when we allow that triangle to be rotated by $π$ radians in addition to being scaled and translated we get a lower bound of $1/768$. In proving this last result, we improve the state of the art on the version of this problem in three dimensions, where $C$ is a parallelepiped. We also consider the algorithmic aspects of finding such a pair of points.

0.13