On the Complexity of Shattering Using Arrangements

Abstract

A subdivision $\cal S$ of $\Re^{d}$ is said to shatter a set of objects if each object is contained within the closure of its own cell of $\cal S$. In this paper, we examine the problem of shattering a set of bounded polyhedral objects in $\Re^{d}$ by a subdivision formed by an arrangement of hyperplanes. We show for $\Re^{d}, d \geq$ 2 that finding a minimum-- cardinality set of hyperplanes whose arrangement shatters a set of points is NP-Complete. We then give algorithms to find a linear-size set of shattering hyperplanes for a set of $n$ bounded polyhedral objects in $\Re^{d}$, if one exists. For $d=2$, we provide two algorithms with worst-case time complexities $O(E+N$log$N+n^{2}$log$n$) and $O(E+N$log$N+C$log$n+nC^{.695})$, where $E$ is the size of the visibility graph of the objects, $N$ is the total number of vertices, and $C$ is the number of candidate lines considered (at worst min\{$E,n^2$\}). Our final algorithm has worst-case time complexity $O(N^{d+1})$ for $d \geq 3$.