Geometric optimization problems on orthogonal polygons: hardness results and approximation algorithms

Simple item page
dc.contributor.authorMehrabidavoodabadi, Saeed
dc.contributor.examiningcommitteeChing Li, Pak (Computer Science) Morrison, Jason (Biosystems Engineering) Keil, Mark (University of Saskatchewan)en_US
dc.contributor.supervisorDurocher, Stephane (Computer Science)en_US
dc.date.accessioned2015-12-22T19:49:25Z
dc.date.available2015-12-22T19:49:25Z
dc.date.issued2015
dc.degree.disciplineComputer Scienceen_US
dc.degree.levelDoctor of Philosophy (Ph.D.)en_US
dc.description.abstractIn 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.en_US
dc.description.noteFebruary 2016en_US
dc.identifier.urihttp://hdl.handle.net/1993/30984
dc.language.isoengen_US
dc.rightsopen accessen_US
dc.subjectOrthogonal art gallery problem, Minimum stabbing number problem, Terrain guarding problem, Approximation algorithmsen_US
dc.titleGeometric optimization problems on orthogonal polygons: hardness results and approximation algorithmsen_US
dc.typedoctoral thesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
MehrabiDavoodabadi_Saeed.pdf
Size:
533.9 KB
Format:
Adobe Portable Document Format
Description:
THIS IS MY UPDATED THESIS UPLOADED ON OCTOBER 7TH.
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.25 KB
Format:
Item-specific license agreed to upon submission
Description:
Download
Collections
FGS - Electronic Theses and Practica