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
﻿