Type
Text
Type
Dissertation
Advisor
Mitchell, Joseph S. B. | Arkin, Esther M. Skiena, Steven | Gao, Jie
Date
2012-08-01
Keywords
Applied mathematics Ð Computer science | Algorithms, Art gallery theorem, Combinatorics, Computational complexity, Computational geometry, Visibility coverage
Department
Department of Applied Mathematics and Statistics
Language
en_US
Source
This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree.
Identifier
http://hdl.handle.net/11401/71273
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
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. | 127 pages
Recommended Citation
Iwerks, Justin Gift, "Combinatorics and complexity in geometric visibility problems" (2012). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 479.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/479