## Nicolas Grelier ; Saeed Gh. Ilchi ; Tillmann Miltzow ; Shakhar Smorodinsky - On the VC-dimension of half-spaces with respect to convex sets

dmtcs:6631 - Discrete Mathematics & Theoretical Computer Science, August 19, 2021, vol. 23, no. 3 - https://doi.org/10.46298/dmtcs.6631
On the VC-dimension of half-spaces with respect to convex sets

Authors: Nicolas Grelier ; Saeed Gh. Ilchi ; Tillmann Miltzow ; Shakhar Smorodinsky

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.

Volume: vol. 23, no. 3
Section: Combinatorics
Published on: August 19, 2021
Accepted on: July 8, 2021
Submitted on: July 10, 2020
Keywords: Computer Science - Computational Geometry,Computer Science - Discrete Mathematics,Computer Science - Data Structures and Algorithms,Mathematics - Combinatorics