Show simple item record

dc.contributor.authorFreimer, Roberten_US
dc.contributor.authorMitchell, Joseph S. B.en_US
dc.contributor.authorPiatko, Christineen_US
dc.date.accessioned2007-04-23T17:52:42Z
dc.date.available2007-04-23T17:52:42Z
dc.date.issued1991-04en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR91-1197en_US
dc.identifier.urihttps://hdl.handle.net/1813/7037
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.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
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

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics