One-sided epsilon-approximants

DOI10.1007/978-3-319-44479-6_12MaRDI QIDQ4604378zbMATHOpenAlexFDO

Authors Boris Bukh, Gabriel Nivasch

Publication date 26 February 2018

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

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

Mathematics Subject Classification ID

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

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$.

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

Cites work

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

Cited in

(4)

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

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)