Partitioning points by parallel planes Original Research Article

A new upper bound is given on the number of ways in which a set of N points in Rn can be partitioned by k parallel hyperplanes. This bound improves upon a result of Olafsson and Abu-Mostafa (IEEE Trans. Pattern Anal. Machine Intell. 10 (2) (1988) 277); it agrees with the known (tight) result for the case k=1; and it is, for fixed k and n, tight to within a constant. A previously published claimed improvement to the bound of Olafsson and Abu-Mostafa is shown to be incorrect.