| dc.identifier.uri | http://hdl.handle.net/1951/59700 | |
| dc.identifier.uri | http://hdl.handle.net/11401/71273 | |
| dc.description.sponsorship | This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree. | en_US |
| dc.format | Monograph | |
| dc.format.medium | Electronic Resource | en_US |
| dc.language.iso | en_US | |
| dc.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dc.type | Dissertation | |
| dcterms.abstract | Geometric visibility is fundamental to computational geometry and its applications in areas such as robotics, sensor networks, CAD, and motion planning. We explore combinatorial and computational complexity problems arising in a collection of settings that depend on various notions of visibility. We first consider a generalized version of the classical art gallery problem in which the input specifies the number of reflex vertices r and convex vertices c of the simple polygon (n = r + c). This additional information better characterizes the shape of the polygon. Through a lower bound construction, tight combinatorial bounds for coverage are achieved for all r >=0 and c >= 3. The combinatorics of guarding polyominoes and other polyforms are studied in terms of m, the number of cells, as opposed to the traditional parameter n. Various visibility models and guard types are considered. We establish that finding a minimum cardinality guard set for covering a polyomino is NP-hard. We introduce an algorithm for constructing a spiral serpentine polygonization of a set of n >= 3 points in the plane. The algorithm's behavior can be viewed as incrementally appending a visible triangle to the triangulation constructed so far. We consider beacon-based point-to-point routing and coverage problems. A beacon b is a point that can be activated to effect a gravitational pull toward itself in a polygonal domain. Algorithms are given for computing the attraction region of b and finding a minimum size set of beacons to route from a source s to a destination t given a finite set of candidate beacon locations. We show that finding a minimum cardinality set of beacons to cover a simple polygon or conduct certain types of routing in a simple polygon is NP-hard. | |
| dcterms.available | 2013-05-22T17:34:49Z | |
| dcterms.available | 2015-04-24T14:46:47Z | |
| dcterms.contributor | Mitchell, Joseph S. B. | en_US |
| dcterms.contributor | Arkin, Esther M. Skiena, Steven | en_US |
| dcterms.contributor | Gao, Jie | en_US |
| dcterms.creator | Iwerks, Justin Gift | |
| dcterms.dateAccepted | 2013-05-22T17:34:49Z | |
| dcterms.dateAccepted | 2015-04-24T14:46:47Z | |
| dcterms.dateSubmitted | 2013-05-22T17:34:49Z | |
| dcterms.dateSubmitted | 2015-04-24T14:46:47Z | |
| dcterms.description | Department of Applied Mathematics and Statistics | en_US |
| dcterms.extent | 127 pg. | en_US |
| dcterms.format | Monograph | |
| dcterms.format | Application/PDF | en_US |
| dcterms.identifier | http://hdl.handle.net/1951/59700 | |
| dcterms.identifier | Iwerks_grad.sunysb_0771E_11012 | en_US |
| dcterms.identifier | http://hdl.handle.net/11401/71273 | |
| dcterms.issued | 2012-08-01 | |
| dcterms.language | en_US | |
| dcterms.provenance | Made available in DSpace on 2013-05-22T17:34:49Z (GMT). No. of bitstreams: 1
Iwerks_grad.sunysb_0771E_11012.pdf: 2371975 bytes, checksum: 07f4b15bce6fb14130ed31d8c61c3887 (MD5)
Previous issue date: 1 | en |
| dcterms.provenance | Made available in DSpace on 2015-04-24T14:46:47Z (GMT). No. of bitstreams: 3
Iwerks_grad.sunysb_0771E_11012.pdf.jpg: 1894 bytes, checksum: a6009c46e6ec8251b348085684cba80d (MD5)
Iwerks_grad.sunysb_0771E_11012.pdf.txt: 213448 bytes, checksum: 6d85afee18548d22afd8402aa347a667 (MD5)
Iwerks_grad.sunysb_0771E_11012.pdf: 2371975 bytes, checksum: 07f4b15bce6fb14130ed31d8c61c3887 (MD5)
Previous issue date: 1 | en |
| dcterms.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dcterms.subject | Applied mathematics Ð Computer science | |
| dcterms.subject | Algorithms, Art gallery theorem, Combinatorics, Computational complexity, Computational geometry, Visibility coverage | |
| dcterms.title | Combinatorics and complexity in geometric visibility problems | |
| dcterms.type | Dissertation | |
