A Non-linear Lower Bound for Planar Epsilon-nets

No abstract is available for this paper.

• Publication year

  2010

• Venue

  Discrete & Computational Geometry

• Publication date

  2010-10-23

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00454-010-9323-7
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Probabilistic Method

  2015cited by this paper
• Wiley‐Interscience Series in Discrete Mathematics and Optimization

  2011cited by this paper
• Density Hales-Jewett and Moser Numbers

  2010cited by this paper
• Improved Approximation for Guarding Simple Galleries from the Perimeter

  2010cited by this paper
• Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes

  2010cited by this paper
• A new proof of the density Hales-Jewett theorem

  2009cited by this paper
• Epsilon Nets and Union Complexity

  2009cited by this paper
• Small-size ε-nets for axis-parallel rectangles and boxes

  2009cited by this paper
• Lower bounds for weak epsilon-nets and stair-convexity

  2008cited by this paper
• The Probabilistic Method, Third Edition

  2008cited by this paper
• The Probabilistic Method: Alon/Probabilistic

  2008cited by this paper
• New existence proofs ε-nets

  2008cited by this paper
• Hitting sets when the VC-dimension is small

  2005cited by this paper
• Indecomposable Coverings

  2005cited by this paper
• Improved Approximation Algorithms for Geometric Set Cover

  2005cited by this paper
• New Constructions of Weak ε-Nets

  2004cited by this paper
• LECTURES ON DISCRETE GEOMETRY (Graduate Texts in Mathematics 212)

  2003cited by this paper
• LECTURES ON DISCRETE GEOMETRY (Graduate Texts in Mathematics 212) By JI MATOUEK: 481 pp., 31.50 (US$39.95), ISBN 0-387-95374-4 (Springer, New York, 2002).

  2003cited by this paper
• Lectures on discrete geometry

  2002cited by this paper
• Transversal numbers for hypergraphs arising in geometry

  2002cited by this paper
• Discrete and Computational Geometry

  2002cited by this paper
• A Density Version of the Hales-Jewett Theorem

  2001cited by this paper
• Almost optimal set covers in finite VC-dimension

  1995cited by this paper
• Combinatorial geometry

  1995cited by this paper
• Traces of finite sets: extremal problems and geometric applications

  1994cited by this paper
• Improved bounds on weak ε-nets for convex sets

  1993cited by this paper
• Almost tight bounds for $\epsilon$-nets

  1992cited by this paper
• Reporting Points in Halfspaces

  1992cited by this paper
• Almost tight bounds forɛ-Nets

  1992influential reference
• Partitioning arrangements of lines I: An efficient deterministic algorithm

  1990cited by this paper
• How to net a lot with little: small ε-nets for disks and halfspaces

  1990cited by this paper
• Some new bounds for Epsilon-nets

  1990cited by this paper
• A density version of the Hales-Jewett theorem for k=3

  1989influential reference
• A deterministic view of random sampling and its use in geometry

  1988cited by this paper
• Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension

  1987cited by this paper
• ɛ-nets and simplex range queries

  1987influential reference
• New applications of random sampling in computational geometry

  1987cited by this paper
• Fast Probabilistic Algorithms for Verification of Polynomial Identities

  1980cited by this paper
• Probabilistic algorithms for sparse polynomials

  1979cited by this paper
• Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities

  1971cited by this paper
• Regularity and Positional Games

  1963cited by this paper
• Combinatorics, Probability and Computing Point Selections and Weak Ε-nets for Convex Hulls Point Selections and Weak E-nets for Convex Hulls

  year unknowncited by this paper

• Erd\H{o}s-Szekeres Maker-Breaker Games

  2025cites this paper
• Extended VC-dimension, and Radon and Tverberg type theorems for unions of convex sets

  2025influential citation
• Online Epsilon Net and Piercing Set for Geometric Concepts

  2024cites this paper
• Stabbing boxes with finitely many axis-parallel lines and flats

  2023cites this paper
• Stronger bounds for weak epsilon-nets in higher dimensions

  2021influential citation
• Coloring the Union of Geometric Hypergraphs

  2021cites this paper
• Practical Approximation Algorithms for Stabbing Special Families of Line Segments with Equal Disks

  2020cites this paper
• Sensor Cover

  2020cites this paper
• MATH 595 Hypergraph Container Method notes February 15 and 18 , 2019 1 Lecture 12 : Lower Bounds for ε-Nets

  2019cites this paper
• An efficient container lemma

  2019cites this paper
• On the VC-dimension of convex sets and half-spaces

  2019cites this paper
• Approximation Algorithms for Piercing Special Families of Hippodromes: An Extended Abstract

  2019cites this paper
• On Weak epsilon-Nets and the Radon Number

  2019influential citation
• On the VC-dimension of half-spaces with respect to convex sets

  2019cites this paper
• Fe b 20 19 On weak ǫ-nets and the Radon number

  2019influential citation
• A Simple Proof of Optimal Epsilon Nets

  2018cites this paper
• An Improved Bound for Weak Epsilon-Nets in the Plane

  2018influential citation
• Forbidden Configurations in Discrete Geometry

  2018cites this paper
• Uniformly Discrete Forests with Poor Visibility

  2018cites this paper
• THE METHOD OF HYPERGRAPH CONTAINERS

  2018cites this paper
• Efficient constant factor approximation algorithms for stabbing line segments with equal disks

  2018cites this paper
• On combinatorial approximation algorithms in geometry

  2018cites this paper
• Epsilon-Approximations & Epsilon-Nets

  2017influential citation
• Uniformly Discrete Forests with Poor Visibility

  2017cites this paper
• Fe b 20 17 47 EPSILON-APPROXIMATIONS & EPSILON-NETS

  2017cites this paper
• 2 01 7 47 EPSILON-APPROXIMATIONS & EPSILON-NETS

  2017cites this paper
• On Weak ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon $$\end{document}-Nets and the Radon Number

  2017cites this paper
• Near-Optimal Lower Bounds for Epsilon-nets for Half-spaces and Low Complexity Set Systems

  2017cites this paper
• On the number of points in general position in the plane

  2017influential citation
• The VC-dimension of Unions : Learning , Geometry and Combinatorics

  2017influential citation
• Near-Optimal Lower Bounds for -nets for Half-spaces and Low Complexity Set Systems

  2017influential citation
• NEW APPROACHES TO SOME PROBLEMS IN DISCRETE GEOMETRY

  2017cites this paper
• A Simple Proof of Optimal Epsilon Nets

  2017cites this paper
• Epsilon-approximations and epsilon-nets

  2017influential citation
• 47 EPSILON-APPROXIMATIONS & EPSILON-NETS

  2016cites this paper
• New Lower Bounds for �-nets

  2016cites this paper
• New Lower Bounds for (cid:15) -nets

  2015cites this paper
• Geometric Hitting Set for Segments of Few Orientations

  2015influential citation
• On Interference Among Moving Sensors and Related Problems

  2015cites this paper
• On Kinetic Range Spaces and their Applications

  2015influential citation
• Approximation and Online Algorithms

  2015cites this paper
• Approximation Algorithms for Hitting Triangle-Free Sets of Line Segments

  2014cites this paper
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers

  2014cites this paper
• Epsilon-Nets for Halfspaces Revisited

  2014cites this paper
• Epsilon-Nets for Halfspaces Revisited

  2014cites this paper
• TIGHT LOWER BOUNDS FOR THE SIZE OF EPSILON-NETS

  2013cites this paper
• On the approximability of covering points by lines and related problems

  2013cites this paper
• Unsplittable Coverings in the Plane

  2013cites this paper
• Approximations of Points: Combinatorics and Algorithms

  2013cites this paper
• Paul Erdős and Probabilistic Reasoning

  2013cites this paper
• TIGHT LOWER BOUNDS FOR THE SIZE OF EPSILON-NETS

  2013cites this paper
• TIGHT LOWER BOUNDS FOR THE SIZE OF EPSILON-NETS

  2013cites this paper
• Computational aspects of some problems from discrete geometry in higher dimensions

  2013cites this paper
• On Epsilon-Nets, Distance Oracles, and Metric Embeddings

  2012cites this paper
• Hardness of discrepancy computation and ε-net verification in high dimension

  2012cites this paper
• Piercing quasi-rectangles - On a problem of Danzer and Rogers

  2012cites this paper
• Minimum entangling power is close to its maximum

  2012cites this paper
• Active and passive learning of linear separators under log-concave distributions

  2012cites this paper
• Small strong epsilon nets

  2012influential citation
• On Covering Points with Conics and Strips in the Plane

  2012cites this paper
• Hardness of discrepancy computation and epsilon-net verification in high dimension

  2011cites this paper
• Grid structures for efficient geometric algorithms

  2011cites this paper
• epsilon-Samples of Kernels

  2011cites this paper
• Є-Samples for Kernels

  2011cites this paper
• Covering Problems via Structural Approaches

  2011cites this paper
• Guarding problems and geometric split trees

  2011cites this paper
• The Dawn of an Algebraic Era in Discrete Geometry?

  2011cites this paper
• Piercing Quasi-Rectangles: On a Problem of Danzer and Rogers

  2011cites this paper
• A note about weak epsilon-nets for axis-parallel boxes in d-space

  2010cites this paper
• New -Net Constructions

  2010cites this paper
• Tight lower bounds for the size of epsilon-nets

  2010cites this paper
• New epsilon-net constructions

  2010cites this paper
• Lower bounds for weak epsilon-nets and stair-convexity

  2008cites this paper