On the VC-dimension of half-spaces with respect to convex sets

DOI10.46298/DMTCS.6631MaRDI QIDQ5024665zbMATH OpenOpenAlexFDO

Authors Nicolas Grelier, Saeed Gh. Ilchi, Tillmann Miltzow, Shakhar Smorodinsky

Publication date 27 January 2022

Published in Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1907.01241, https://dmtcs.episciences.org/8376

zbMATH Keywords

\textsf{VC}-dimensionconvex setsepsilon netshalfplanes

Mathematics Subject Classification ID

Hypergraphs (05C65) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• The VC-dimension of K-vertex D-polytopes
• Tight lower bounds on the VC-dimension of geometric set systems
• Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
• On the transversal number and VC-dimension of families of positive homothets of a convex body
• Bounded VC-dimension implies a fractional Helly theorem

Cited in

(3)

• On VV-singular boundary sets of arbitrary mappings of multidimensional half-spaces
• The \(\varepsilon\)-\(t\)-net problem
• A note on VC-dimension and measure of sets of reals

This page was built for publication: On the VC-dimension of half-spaces with respect to convex sets

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