轴对齐矩形 — VC 维 = 4

上级：examples 前置：learning-theory —— H、h、打散（shattering）。

所有轴对齐矩形 [a₁,b₁]×[a₂,b₂] 构成的类，共有四个参数：

计数。 取上、下、左、右四个极值点（构成一个小菱形）。对任意一种标记方式，取恰好包住所有 + 点的最紧矩形；它的 4 条边可以独立地推动，把每个极值点纳入或排除在外 → 所有 2⁴ = 16 种标记都可实现 → 打散了 4 个点 → VC ≥ 4。

对任意 5 个点：取其中最上、最下、最左、最右的点（至多 4 个不同的点）；把这 4 个点标为 +，剩下那个点标为 −。任何覆盖住这 4 个极值点的矩形，都必然覆盖它们的外接边界框，而这个边界框也包含第 5 个点 → 它被迫也标成 + → 这种标记无法实现 → 没有 5 个点能被打散 → VC = 4。