On the VC-dimension of convex sets and half-spaces

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

Research output: Contribution to journalArticleAcademic

Abstract

A family $S$ of convex sets in the plane defines a hypergraph $H = (S,E)$ as follows. Every subfamily $S'\subset 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 \emph{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 also show that the VC-dimension is unbounded for pairwise disjoint convex sets in $\mathbb{R}^d$, for $d\geq 3$. 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.
Original languageEnglish
Number of pages11
JournalarXiv.org
Publication statusPublished - 2 Jul 2019

Bibliographical note

11 pages, 9 figures

Keywords

  • cs.CG
  • cs.DM
  • cs.DS
  • math.CO

Fingerprint

Dive into the research topics of 'On the VC-dimension of convex sets and half-spaces'. Together they form a unique fingerprint.

Cite this