Axis-aligned rectangles — VC = 4

Parent: examples Prereq: learning-theory — H, h, shattering.

Class of all axis-aligned rectangles [a₁,b₁]×[a₂,b₂], four parameters:

h(x) = \begin{cases} + & a_1 \le x_1 \le b_1 \ \text{and}\ a_2 \le x_2 \le b_2 \\ - & \text{otherwise} \end{cases}

Count. Take 4 points at the top/bottom/left/right extremes (a small diamond). For any labeling, take the tightest rectangle enclosing the + points; each of its 4 sides can be pushed independently to include or exclude one extreme → all 2⁴ = 16 labelings realizable → shatters 4 → VC ≥ 4.

For any 5 points: pick the topmost, bottommost, leftmost, rightmost (≤ 4 distinct); label those 4 + and the remaining point −. Any rectangle covering the 4 extremes covers their bounding box, which contains the 5th point too → it's forced + → that labeling fails → no 5 shatter → VC = 4.