Piercing problems arise often in facility location, which is a well-studied area of computational geometry. The general form of the piercing problem discussed in this dissertation asks for the minimum number of facilities for a set of given rectangular demand regions such that each region has at least one facility located within it. It has been shown that even if all regions are uniform sized squares, the problem is NP-hard. Therefore we concentrate on approximation algorithms for the problem. As the known approximation ratio for arbitrarily sized rectangles is poor, we restrict our effort to designing approximation algorithms for unit-height rectangles. Our e-approximation scheme requires <I>n</I>^{<I>O</I>(1/&epsilon;??)} time. We also consider the problem with restrictions like bounding the depth of a point and the width of the rectangles. The approximation schemes for these two cases take <I>n</I>^{<I>O</I>(1/&epsilon;)} time. We also show how to maintain a factor 2 approximation of the piercing set in <I>O</I>(log <I>n</I>) amortized time in an insertion-only scenario.

Iris Fitzgerald struggles to make it day to day after she is raped and stabbed while out on an early morning run. Her story is told through her relationships, not only with her new, scared self, but also with her overbearing mother, her best friend, her rescuer and her antagonistic roommate. She has just moved to a strange city and still has not found a job. So, she has the overwhelming stress of the attack to contend with and the added pressure of running quickly out of money in the expensive city of San Francisco. She uses her painkillers as an escape from her stab wound as well as her emotional pain. Claiming Iris is about self-preservation, relationships, addiction and continuing on with life.

No description available.

Piercing problems arise often in facility location, which is a well-studied area of computational geometry. The general form of the piercing problem discussed in this dissertation asks for the minimum number of facilities for a set of given rectangular demand regions such that each region has at least one facility located within it. It has been shown that even if all regions are uniform sized squares, the problem is NP-hard. Therefore we concentrate on approximation algorithms for the problem. As the known approximation ratio for arbitrarily sized rectangles is poor, we restrict our effort to designing approximation algorithms for unit-height rectangles. Our e-approximation scheme requires <I>n</I>^{<I>O</I>(1/&epsilon;²)} time. We also consider the problem with restrictions like bounding the depth of a point and the width of the rectangles. The approximation schemes for these two cases take <I>n</I>^{<I>O</I>(1/&epsilon;)} time. We also show how to maintain a factor 2 approximation of the piercing set in <I>O</I>(log <I>n</I>) amortized time in an insertion-only scenario.

In this thesis, we design and develop new approximation algorithms and complexity results for three guarding and partitioning problems on orthogonal polygons; namely, guarding orthogonal polygons using sliding cameras, partitioning orthogonal polygons so as to minimize the stabbing number and guarding orthogonal terrains using vertex guards. We first study a variant of the well-known art gallery problem in which sliding cameras are used to guard the polygon. We consider two versions of this problem: the Minimum- Cardinality Sliding Cameras (MCSC) problem in which we want to guard P with the minimum number of sliding cameras, and the Minimum-Length Sliding Cameras (MLSC) problem in which the goal is to compute a set S of sliding cameras for guarding P so as to minimize the total length of trajectories along which the cameras in S travel. We answer questions posed by Katz and Morgenstern (2011) by presenting the following results: (i) the MLSC problem is polynomially tractable even for orthogonal polygons with holes, (ii) the MCSC problem is NP-complete when P is allowed to have holes, and (iii) an O(n)-time exact algorithm for the MCSC problem on monotone polygons. We then study a conforming variant of the problem of computing a partition of an orthogonal polygon P into rectangles whose stabbing number is minimum over all such partitions of P. The stabbing number of such a partition is the maximum number of rectangles intersected by any orthogonal line segment inside the polygon. In this thesis, we first give an O(n log n)-time algorithm that solves this problem exactly on histograms. We then show that the problem is NP-hard for orthogonal polygons with holes, providing the first hardness result for this problem. To complement the NP-hardness result, we give a 2-approximation algorithm for the problem on both polygons with and without holes. Finally, we study a variant of the terrain guarding problem on orthogonal terrains in which the objective is to guard the vertices of an orthogonal terrain with the minimum number of vertex guards. We give a linear-time algorithm for this problem under a directed visibility constraint. / February 2016

No description available.