Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning

DOI10.1007/s00454-019-00075-0zbMath1433.68492OpenAlexW2921474644MaRDI QIDQ2415378

Kunal Dutta, Nabil H. Mustafa, Arijit Ghosh, Bruno Jartoux

Publication date: 21 May 2019

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7199/

zbMATH Keywords

shallow-cell complexityepsilon-netsshallow packing lemmaHaussler's packing lemmaMnets

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial probability (60C05) Combinatorial aspects of packing and covering (05B40) Combinatorial complexity of geometric structures (52C45)

Related Items (1)

The \(\varepsilon\)-\(t\)-net problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple proof of the shallow packing lemma
• On the Erdős distinct distances problem in the plane
• \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets
• Two proofs for shallow packings
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
• Applications of random sampling in computational geometry. II
• Multilevel polynomial partitions and simplified range searching
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• A semi-algebraic version of Zarankiewicz's problem
• Topological Hypergraphs
• Optimal area-sensitive bounds for polytope approximation
• On the set multicover problem in geometric settings
• Convex bodies, economic cap coverings, random polytopes
• Fat Triangles Determine Linearly Many Holes
• Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems
• Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
• Improved Bounds for the Union of Locally Fat Objects in the Plane
• A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension
• Geometric discrepancy. An illustrated guide
• Algorithms in real algebraic geometry
• Improved bounds on the sample complexity of learning

This page was built for publication: Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning