One-sided epsilon-approximants

DOI10.1007/978-3-319-44479-6_12zbMATH Open1387.05178arXiv1603.05717OpenAlexW2299788535MaRDI QIDQ4604378FDOQ4604378

Authors: Boris Bukh, Gabriel Nivasch 

Publication date: 26 February 2018

Published in: A Journey Through Discrete Mathematics (Search for Journal in Brave)

Abstract: Given a finite point set $Psubsetmathbb{R}^d$, we call a multiset $A$ a one-sided weak $varepsilon$-approximant for $P$ (with respect to convex sets), if $|PcapC|/|P|-|AcapC|/|A|leqvarepsilon$ for every convex set $C$. We show that, in contrast with the usual (two-sided) weak $varepsilon$-approximants, for every set $Psubsetmathbb{R}^d$ there exists a one-sided weak $varepsilon$-approximant of size bounded by a function of $varepsilon$ and $d$.

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

Recommendations

• New constructions of weak epsilon-nets
• New constructions of weak \(\varepsilon\)-nets
• Improved bounds on weak \(\varepsilon\)-nets for convex sets
• Small weak epsilon-nets
• A lower bound for weak \(\varepsilon\)-nets in high dimension

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Hypergraphs (05C65) Graph theory (05C99)

Cites Work

• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Lectures on Polytopes
• \(\epsilon\)-nets and simplex range queries
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Geometric discrepancy. An illustrated guide
• A deterministic view of random sampling and its use in geometry
• Title not available (Why is that?)
• Overlap properties of geometric expanders
• A regularity lemma and twins in words
• Stabbing simplices by points and flats
• A note on order-type homogeneous point sets
• Lower bounds on geometric Ramsey functions
• Lower bounds for weak epsilon-nets and stair-convexity
• Point Selections and Weak ε-Nets for Convex Hulls
• A Randomized Algorithm for Closest-Point Queries
• Geometric methods in the study of irregularities of distribution
• Tight upper bounds for the discrepancy of half-spaces
• Title not available (Why is that?)
• A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
• A limit theorem for sets of stochastic matrices.
• Curves in \(\mathbb{R}^d\) intersecting every hyperplane at most \(d+1\) times
• Chasing Ghosts: Competing with Stateful Policies

Cited In (4)

• Tverberg’s theorem is 50 years old: A survey
• Extending the centerpoint theorem to multiple points
• Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1
• Some converse results on onesided approximation: Justifications

This page was built for publication: One-sided epsilon-approximants

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