Facet lower bound for ball approximations 2026-10-06
If and a convex polytope satisfies , then it has at least facets. Its outward facet normals define spherical caps covering the unit sphere; the spherical cap area upper bound supplies the estimate.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 112 2 iii Solution Created 2026-10-03 Updated 2026-10-06
Let be the number of facets of the convex polytope . Its facet description can be writtenBecause , each supporting closed half-space has . For any , follow the ray to its last point in . Its radius is at most one because . At least one facet is active there, givingThus the unit sphere is covered by the spherical caps centred at with angular radius . Since , this radius lies in and the spherical cap area upper bound applies. Subadditivity of surface area givesUsing for ,The facet lower bound for ball approximations is exponential in the dimension.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 112 2 iv Solution Created 2026-10-03 Updated 2026-10-06
Choose a maximal subset whose distinct points have Euclidean distance greater than one. The volumetric bound for Euclidean metric nets makes the construction finite: the open Euclidean balls of radius about the points of are disjoint and all lie in , soMaximality means that is a metric net of radius one on the unit sphere. Thus every has some with . Since both are unit vectors,Now intersect the corresponding closed half-spaces:The Cauchy-Schwarz inequality shows that . Conversely, write any nonzero as and choose as above. Then , so . Hence , which also proves boundedness. This convex polytope has at most facets, since redundant inequalities can only reduce their number. It meets the required inclusions with .