Almost tight bounds for \(\epsilon\)-nets
From MaRDI portal
Publication:1184160
DOI10.1007/BF02187833zbMath0765.68209OpenAlexW2064561047WikidataQ56853082 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)
Related Items
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, 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, 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., 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
Cites Work
- 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
- Unnamed Item
