Shattering Configurations of Points With Hyperplanes.
An arrangement of hyperplanes $\cal A$ in $\Re^d$ is said to shatter a point set $\cal O$ if each point of $\cal O$ is contained within the interior of its own cell of $\cal A$. In this paper, we investigate the number of hyperplanes required by an arrangement that shatters a set of $n$ points in general position. We show that such sets can require between $\Omega(\sqrt[d]{n})$ and $\Omega(n)$ shattering hyperplanes. We also provide an algorithm that finds a linear-size shattering for such sets. The number of hyperplanes produced exceeds the requirements of the worst known example in $\Re^d$ by at most constant, which depends only on $d$. We also give some results for when the points are in general convex position.