示例 3.15 凸 d-边形类

我们讨论平面上的凸 $d$-边形类。

• 首先，给出一个下界，
  • 展示任意 (2d + 1) 个点可以被打散。
• 为此，我们选择 (2d + 1) 个点位于一个圆上。
• 对于某个特定的标记，
  • 如果负标签的点多于正标签的点，
    • 那么带正标签的点作为多边形的顶点，
      • 如图 3.4(a) 所示。
    • 否则，带负标签的点的切线作为多边形的边，
      • 如图 3.4(b) 所示。

Figure 3.4 平面上的凸 $d$ -边形可以打散 $2d+1$ 个点。

• (a) 当负标签较多时的 $d$-边形构造。
• (b) 当正标签较多时的 $d$-边形构造。

为了给出上界，可以证明选择圆上的点能够最大化可能的二分法数，因此 $\mathrm{VCdim}(\text{convex }d\text{-gons})=2d+1$

Remark

还可以注意到 $\mathrm{VCdim}(\text{convex polygons})=+\infty$ 因为凸多边形的边数没有限制，任意数量的点都可以被凸多边形打散。