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.
翻译:平面上的共形家庭S 定义高光 H = (S, E) 如下。 S 的每个子家庭S 定义 H 的顶部, 如果并且只有存在半空 h 完全包含 S ”, 而没有其它的 S 组完全包含在 h 中。 在这种情况下, 我们说 h 实现 S 。 我们说, 如果它的所有子集都实现, 一个 S 组的 S 组被粉碎。 高光 H 的 VC 分解是最大的碎裂集的大小 。 我们显示, 平面上对齐脱节的共形的 VC 分解组被 3 捆绑在一起, 并且这是很紧的 H。 相比之下, 我们显示平面上的 VC 组( 不一定脱节) 的 VC 分层, 我们的分层 将分解为两段 。