Almost tight bounds for \(\epsilon\)-nets
From MaRDI portal
Publication:1184160
DOI10.1007/BF02187833zbMath0765.68209DBLPjournals/dcg/KomlosPW92OpenAlexW2064561047WikidataQ56853082 ScholiaQ56853082MaRDI QIDQ1184160
János Pach, János Komlós, Gerhard J. Woeginger
Publication date: 28 June 1992
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131188
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- Unnamed Item
- Combinatorial complexity bounds for arrangements of curves and spheres
- Covering the plane with convex polygons
- \(\epsilon\)-nets and simplex range queries
- New applications of random sampling in computational geometry
- Quasi-optimal range searching in spaces of finite VC-dimension
- On the density of families of sets
- Learnability and the Vapnik-Chervonenkis dimension
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Related Items (55)
Tighter estimates for \(\epsilon\)-nets for disks ⋮ Optimal approximations made easy ⋮ On range searching with semialgebraic sets ⋮ Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements ⋮ Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces ⋮ Minimum entangling power is close to its maximum ⋮ Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications ⋮ Almost optimal set covers in finite VC-dimension ⋮ On the geometric set multicover problem ⋮ The \(\varepsilon\)-\(t\)-net problem ⋮ Quasi-Monte-Carlo methods and the dispersion of point sequences ⋮ A new upper bound for the VC-dimension of visibility regions ⋮ Erdős-Hajnal conjecture for graphs with bounded VC-dimension ⋮ Small strong epsilon nets ⋮ Domination in transitive colorings of tournaments ⋮ Stronger bounds for weak epsilon-nets in higher dimensions ⋮ Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location ⋮ A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space ⋮ Relative \((p,\varepsilon )\)-approximations in geometry ⋮ System of unbiased representatives for a collection of bicolorings ⋮ Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems ⋮ An optimal generalization of the colorful Carathéodory theorem ⋮ Improved approximation for guarding simple galleries from the perimeter ⋮ Piercing quasi-rectangles-on a problem of Danzer and Rogers ⋮ An application of the universality theorem for Tverberg partitions to data depth and hitting convex sets ⋮ Practical and efficient algorithms for the geometric hitting set problem ⋮ Sign rank versus Vapnik-Chervonenkis dimension ⋮ A Sauer-Shelah-Perles lemma for lattices ⋮ Random polytopes and the wet part for arbitrary probability distributions ⋮ Polychromatic coloring for half-planes ⋮ Approximating Nonnegative Polynomials via Spectral Sparsification ⋮ Approximating a convex body by a polytope using the epsilon-net theorem ⋮ A non-linear lower bound for planar epsilon-nets ⋮ Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions. ⋮ On the number of points in general position in the plane ⋮ Pseudofinite groups and VC-dimension ⋮ \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets ⋮ Tight lower bounds for the size of epsilon-nets ⋮ Combinatorial optimization algorithms for radio network planning ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A bicriteria approximation algorithm for the minimum hitting set problem in measurable range spaces ⋮ Hitting sets when the shallow cell complexity is small ⋮ A note on the \(k\)-restriction problem ⋮ Random constructions and density results ⋮ An efficient container lemma ⋮ When are epsilon-nets small? ⋮ Small weak epsilon-nets ⋮ Guarding galleries where no point sees a small area. ⋮ Tverberg partitions as weak epsilon-nets ⋮ Hitting sets when the VC-dimension is small ⋮ Quantitative structure of stable sets in arbitrary finite groups ⋮ An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries ⋮ Transversal numbers for hypergraphs arising in geometry ⋮ Bounding the vertex cover number of a hypergraph
This page was built for publication: Almost tight bounds for \(\epsilon\)-nets
