Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On the VC-dimension of half-spaces with respect to convex sets   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.

31
The categories of this paper are: ao-sci
13
The categories of this paper are: quant-ph
17
The categories of this paper are: q-fin
37
The categories of this paper are: supr-con
20
The categories of this paper are: acc-phys
19
The categories of this paper are: eess
9
The categories of this paper are: nlin
4
The categories of this paper are: cond-mat
18
The categories of this paper are: econ
25
The categories of this paper are: patt-sol
35
The categories of this paper are: mtrl-th
16
The categories of this paper are: stat
29
The categories of this paper are: funct-an
3
The categories of this paper are: physics
27
The categories of this paper are: comp-gas
26
The categories of this paper are: bayes-an