On intersecting a point set with Euclidean balls

✍ Scribed by Daniel Q. Naiman; Henry P. Wynn

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 518 KB
• Volume: 7
• Category: Article
• ISSN: 0925-7721
• DOI: 10.1016/0925-7721(95)00037-2

✦ Synopsis

The growth function for a class of subsets C of a set X is defined by m'(N) = max {AC(F): F G X, IFI = N} , N = 1,2,. . . , where AC(F) = ({F n C: C E C}l, 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 V(C)-1 mC(N) < c 7 0 for N > V(C) -1. j=o 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.