Lower bounds for weak epsilon-nets and stair-convexity

DOI10.1145/1542362.1542365zbMATH Open1222.68395arXiv0812.5039OpenAlexW2567966754MaRDI QIDQ532609FDOQ532609

Authors: Boris Bukh, Gabriel Nivasch, Jiří Matoušek 

Publication date: 5 May 2011

Published in: Israel Journal of Mathematics, Proceedings of the twenty-fifth annual symposium on Computational geometry (Search for Journal in Brave)

Abstract: A set N is called a "weak epsilon-net" (with respect to convex sets) for a finite set X in R^d if N intersects every convex set that contains at least epsilon*|X| points of X. For every fixed d>=2 and every r>=1 we construct sets X in R^d for which every weak (1/r)-net has at least Omega(r log^{d-1} r) points; this is the first superlinear lower bound for weak epsilon-nets in a fixed dimension. The construction is a "stretched grid", i.e., the Cartesian product of d suitable fast-growing finite sequences, and convexity in this grid can be analyzed using "stair-convexity", a new variant of the usual notion of convexity. We also consider weak epsilon-nets for the diagonal of our stretched grid in R^d, d>=3, which is an "intrinsically 1-dimensional" point set. In this case we exhibit slightly superlinear lower bounds (involving the inverse Ackermann function), showing that upper bounds by Alon, Kaplan, Nivasch, Sharir, and Smorodinsky (2008) are not far from the truth in the worst case. Using the stretched grid we also improve the known upper bound for the so-called "second selection lemma" in the plane by a logarithmic factor: We obtain a set T of t triangles with vertices in an n-point set in the plane such that no point is contained in more than O(t^2 / (n^3 log (n^3/t))) triangles of T.

Full work available at URL: https://arxiv.org/abs/0812.5039

Recommendations

• Lower bounds for weak epsilon-nets and stair-convexity
• Improved bounds on weak \(\varepsilon\)-nets for convex sets
• Point Selections and Weak ε-Nets for Convex Hulls
• A lower bound for weak \(\varepsilon\)-nets in high dimension
• A note on stabbing convex bodies with points, lines, and flats

zbMATH Keywords

computational geometrylower boundsinverse Ackermann functionselection lemmastair-convexitystaircase convexityweak epsilon-net

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55)

Cites Work

• \(\epsilon\)-nets and simplex range queries
• Title not available (Why is that?)
• On irregularities of distribution
• Geometric discrepancy. An illustrated guide
• A non-linear lower bound for planar epsilon-nets
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• Transversal numbers for hypergraphs arising in geometry
• Stabbing simplices by points and flats
• Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
• Improved bounds on weak \(\varepsilon\)-nets for convex sets
• Weak \(\varepsilon\)-nets for points on a hypersphere
• Point Selections and Weak ε-Nets for Convex Hulls
• A lower bound for weak \(\varepsilon\)-nets in high dimension
• Improved bounds for intersecting triangles and halving planes
• On the number of halving planes
• Eppstein's bound on intersecting triangles revisited
• Staircase connected sets
• Title not available (Why is that?)

Cited In (33)

• Lower bounds for weak epsilon-nets and stair-convexity
• Small strong epsilon nets
• A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space
• On piercing numbers of families satisfying the \((p,q)_{r}\) property
• Tight bounds for conflict-free chromatic guarding of orthogonal art galleries
• Universal point sets for planar three-trees
• Improved bounds on the Hadwiger-Debrunner numbers
• Upper bounds for stabbing simplices by a line
• Improved bounds on weak \(\varepsilon\)-nets for convex sets
• Stronger bounds for weak epsilon-nets in higher dimensions
• New constructions of weak \(\varepsilon\)-nets
• Radon numbers and the fractional Helly theorem
• A lower bound for weak \(\varepsilon\)-nets in high dimension
• Universal sequences of lines in \(\mathbb{R}^d\)
• A variant of the Hadwiger-Debrunner \((p,q)\)-problem in the plane
• Helly-type problems
• On weak \(\epsilon\)-nets and the Radon number
• Some new results on geometric transversals
• A non-linear lower bound for planar epsilon-nets
• Tverberg’s theorem is 50 years old: A survey
• A note on stabbing convex bodies with points, lines, and flats
• Title not available (Why is that?)
• New constructions of weak epsilon-nets
• New Lower Bounds for ϵ-nets
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Space crossing numbers
• A new lower bound on Hadwiger-Debrunner numbers in the plane
• Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1
• Universal geometric graphs
• One-sided epsilon-approximants
• A new lower bound on Hadwiger-Debrunner numbers in the plane
• Further consequences of the colorful Helly hypothesis
• Positive-fraction intersection results and variations of weak epsilon-nets

This page was built for publication: Lower bounds for weak epsilon-nets and stair-convexity

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