Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 1 / 31J / d

For one real coordinate, a union of $m$ intervals labels a fixed $n$-point sample by choosing at most $2m$ endpoints among the $n+1$ gaps, so the number of labelings is at most $(n+1{)}^{2m}$. Membership in a Cartesian product is the product of the $p$ coordinate-membership indicators. Applying part (c) repeatedly gives

A convex polygon with $m$ sides is an intersection of $m$ affine half-planes. Affine half-plane indicators in ${\mathbb{R}}^2$ have VC dimension at most $3$, so the Sauer-Shelah growth bound gives at most $(n+1{)}^3$ labelings on $n$ points. An intersection corresponds to the coordinatewise product of its $m$ half-plane indicators. Repeated use of part (c) therefore gives