Lower bounds for weak epsilon-nets and stair-convexity

DOI10.1007/s11856-011-0029-1zbMath1222.68395arXiv0812.5039OpenAlexW2567966754MaRDI QIDQ532609

Gabriel Nivasch, Boris Bukh, 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)

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

zbMATH Keywords

lower boundscomputational geometryinverse Ackermann functionstaircase convexityweak epsilon-netselection lemmastair-convexity

Mathematics Subject Classification ID

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

Related Items (23)

On piercing numbers of families satisfying the \((p,q)_{r}\) property ⋮ Tight bounds for conflict-free chromatic guarding of orthogonal art galleries ⋮ Space Crossing Numbers ⋮ Improved bounds on the Hadwiger-Debrunner numbers ⋮ Small strong epsilon nets ⋮ A note on stabbing convex bodies with points, lines, and flats ⋮ Further consequences of the colorful Helly hypothesis ⋮ Universal sequences of lines in \(\mathbb{R}^d\) ⋮ A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space ⋮ One-Sided Epsilon-Approximants ⋮ Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1 ⋮ On weak \(\epsilon\)-nets and the Radon number ⋮ A non-linear lower bound for planar epsilon-nets ⋮ Upper bounds for stabbing simplices by a line ⋮ Positive-fraction intersection results and variations of weak epsilon-nets ⋮ Universal point sets for planar three-trees ⋮ Radon numbers and the fractional Helly theorem ⋮ Unnamed Item ⋮ Tverberg’s theorem is 50 years old: A survey ⋮ A variant of the Hadwiger-Debrunner \((p,q)\)-problem in the plane ⋮ A new lower bound on Hadwiger-Debrunner numbers in the plane ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Helly-type problems

Cites Work

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

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