Decomposing polygons into r-stars or alpha-bounded subpolygons

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.