JavaScript is disabled for your browser. Some features of this site may not work without it.
On the Complexity of Shattering Using Arrangements
dc.contributor.author | Freimer, Robert | en_US |
dc.contributor.author | Mitchell, Joseph S. B. | en_US |
dc.contributor.author | Piatko, Christine | en_US |
dc.date.accessioned | 2007-04-23T17:52:42Z | |
dc.date.available | 2007-04-23T17:52:42Z | |
dc.date.issued | 1991-04 | en_US |
dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR91-1197 | en_US |
dc.identifier.uri | https://hdl.handle.net/1813/7037 | |
dc.description.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$. | en_US |
dc.format.extent | 2532067 bytes | |
dc.format.extent | 546158 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | application/postscript | |
dc.language.iso | en_US | en_US |
dc.publisher | Cornell University | en_US |
dc.subject | computer science | en_US |
dc.subject | technical report | en_US |
dc.title | On the Complexity of Shattering Using Arrangements | en_US |
dc.type | technical report | en_US |