Show simple item record

dc.contributor.authorFreimer, Roberten_US
dc.contributor.authorMitchell, Joseph S. B.en_US
dc.contributor.authorPiatko, Christineen_US
dc.description.abstractA 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$.en_US
dc.format.extent2532067 bytes
dc.format.extent546158 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleOn the Complexity of Shattering Using Arrangementsen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record