dc.contributor.advisor Keil, J. Mark en_US dc.creator Worman, Chris en_US dc.date.accessioned 2004-08-03T19:47:07Z en_US dc.date.accessioned 2013-01-04T04:50:17Z dc.date.available 2004-08-09T08:00:00Z en_US dc.date.available 2013-01-04T04:50:17Z dc.date.created 2004-05 en_US dc.date.issued 2004-05-28 en_US dc.date.submitted May 2004 en_US dc.identifier.uri http://hdl.handle.net/10388/etd-08032004-194707 en_US dc.description.abstract To make computations on large data sets more efficient, algorithms will frequently divide information into smaller, more manageable, pieces. This idea, for example, forms the basis of the common algorithmic approach known as Divide and Conquer. If we wish to use this principle in planar geometric computations, however, we may require specialized techniques for decomposing our data. This is due to the fact that the data sets are typically points, lines, regions, or polygons. This motivates algorithms that can break-up polygons into simpler pieces. Algorithms that perform such computations are said to compute polygon decompositions. There are many ways that we can decompose a polygon, and there are also many types of polygons that we could decompose. Both applications and theoretical interest demand algorithms for a wide variety of decomposition problems. In this thesis we study two different polygon decomposition problems. The first problem that we study is a polygon decomposition problem that is equivalent to the Rectilinear Art Gallery problem. In this problem we seek a decomposition of a polygon into so-called r-stars. These r-stars model visibility in an orthogonal setting. We show that we can compute a certain type of decomposition, known as a Steinercover, of a simple orthogonal polygon into r-stars in polynomial time. In the second problem, we explore the complexity of decomposing polygons into components that have an upper bound on their size. In this problem, the size of a polygon refers to the size of its bounding-box. This problem is motivated by a polygon collision detection heuristic that approximates a polygon by its bounding-box to determine whether an exact collision detection computation should take place. We show that it is NP-complete to decide whether a polygon that contains holes can be decomposed into a specified number of size-constrained components. en_US dc.language.iso en_US en_US dc.subject polygon covering en_US dc.subject art gallery en_US dc.subject polygon decomposition en_US dc.title Decomposing polygons into r-stars or alpha-bounded subpolygons en_US thesis.degree.department Computer Science en_US thesis.degree.discipline Computer Science en_US thesis.degree.grantor University of Saskatchewan en_US thesis.degree.level Masters en_US thesis.degree.name Master of Science (M.Sc.) en_US dc.type.material text en_US dc.type.genre Thesis en_US dc.contributor.committeeMember Mould, David en_US dc.contributor.committeeMember Cheston, Grant A. en_US dc.contributor.committeeMember Neufeld, Eric en_US
﻿