Geodesic
On the VC-dimension of half-spaces with respect to convex sets
Discrete mathematics & theoretical computer science, Tome 23 (2021-2022) no. 3.

Voir la notice de l'article provenant de la source Episciences

A family S of convex sets in the plane defines a hypergraph H = (S, E) as follows. Every subfamily S' of S defines a hyperedge of H if and only if there exists a halfspace h that fully contains S' , and no other set of S is fully contained in h. In this case, we say that h realizes S'. We say a set S is shattered, if all its subsets are realized. The VC-dimension of a hypergraph H is the size of the largest shattered set. We show that the VC-dimension for pairwise disjoint convex sets in the plane is bounded by 3, and this is tight. In contrast, we show the VC-dimension of convex sets in the plane (not necessarily disjoint) is unbounded. We provide a quadratic lower bound in the number of pairs of intersecting sets in a shattered family of convex sets in the plane. We also show that the VC-dimension is unbounded for pairwise disjoint convex sets in R^d , for d > 2. We focus on, possibly intersecting, segments in the plane and determine that the VC-dimension is always at most 5. And this is tight, as we construct a set of five segments that can be shattered. We give two exemplary applications. One for a geometric set cover problem and one for a range-query data structure problem, to motivate our findings.
DOI : 10.46298/dmtcs.6631
Classification : 05C65, 68U05 
@article{DMTCS_2021_23_3_a0,
     author = {Grelier, Nicolas and Ilchi, Saeed Gh. and Miltzow, Tillmann and Smorodinsky, Shakhar},
     title = {On the {VC-dimension} of half-spaces with respect to convex sets},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {23},
     number = {3},
     year = {2021-2022},
     doi = {10.46298/dmtcs.6631},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6631/}
}
TY  - JOUR
AU  - Grelier, Nicolas
AU  - Ilchi, Saeed Gh.
AU  - Miltzow, Tillmann
AU  - Smorodinsky, Shakhar
TI  - On the VC-dimension of half-spaces with respect to convex sets
JO  - Discrete mathematics & theoretical computer science
PY  - 2021-2022
VL  - 23
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6631/
DO  - 10.46298/dmtcs.6631
LA  - en
ID  - DMTCS_2021_23_3_a0
ER  - 
%0 Journal Article
%A Grelier, Nicolas
%A Ilchi, Saeed Gh.
%A Miltzow, Tillmann
%A Smorodinsky, Shakhar
%T On the VC-dimension of half-spaces with respect to convex sets
%J Discrete mathematics & theoretical computer science
%D 2021-2022
%V 23
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6631/
%R 10.46298/dmtcs.6631
%G en
%F DMTCS_2021_23_3_a0
Grelier, Nicolas; Ilchi, Saeed Gh.; Miltzow, Tillmann; Smorodinsky, Shakhar. On the VC-dimension of half-spaces with respect to convex sets. Discrete mathematics & theoretical computer science, Tome 23 (2021-2022) no. 3. doi : 10.46298/dmtcs.6631. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6631/

Cité par Sources :