On intersecting a point set with Euclidean balls
Daniel Q. Naiman, Henry P. Wynn · Computational Geometry · 1997
The growth function for a class of subsets C of a set X is defined by mC(N)max{Δc(F): F⫅X, |F| =N}, N=1,2,…, whereΔc(F)|{F∩C: CϵC}| the number of possible sets obtained by intersecting an element of C with the set F. Sauer (1972) showed that if C forms a Vapnik-Chervonenkis class with dimension V(C), then mc(N)⩽∑j=0V(C)−1Njfor N⩾ V(C) −1. The collection C of Euclidean balls in Rd has been shown by Dudley (1979) to have VC dimension equal to d + 2. It is well known, by using a standard geometric transformation, that Sauer's bound gives the exact number of subsets in this case. We give a more direct construction of the subsets picked out by balls, and as a corollary we obtain the number of such subsets.