ART GALLERY PROBLEMS INTRODUCTION Problem(Klee) Imagine an art gallery room whose floor plan van be modelled by a polygon of n vertices. Question : How many stationary guards are needed to guard the room?

Note that, each guard is constrained a fixed point that can see in every direction, that is, has a 2π range of

visibility. A guard can not see through a wall of the room. The Minimal Guard Coverage Problem has four input components Decomposition Type Shape of Component Pieces Guard’s Place Polygon Restrictions

DECOMPOSING A POLYGON INTO STAR-SHAPED POLYGONS WITHOUT STEINER POINTS

Problem : Partition the polygon into star-shaped polygons without steiner points was studied by the Keil(1984,1985). He proposed a polynomial time algorithm by using the dynamic programming approach.

The complexity of his algorithm is O(n^{7} log n). We will try to implement this algorithm with parallel

approach.

2. KEIL’S ALGORITHM

The algorithm composed of two parts: preporocessing and Dynamic Programming. 2.1 Preprocessing

1. Form the set KER of potential kernel vertices.

2. For each point x ∈ KER store a list of the vertices of P that are visible from x.

3. For each vertex v of P determine the set of vertices of P that are visible from v and store them in a sorted list.

4. Since each visibility pair v_{i}v_{j} (i < j) determined in step 3 is the base edge of a subpolygon these subpolygons can be sorted by the size measure j − i in time O(n^{2} log n).

5. For each subpolygon P_{ij} of P form the set of base triangles with base edge v_{i}v_{j}. ( I think I can directly find this triangles by grouping the vertices of the subpolygon without applying the algorithm I gave)

2.2 Dynamic Programming Part

1. Consider each subpolygon P_{ij} in the order computed in step 4 of the preprocessing.

2. Compute the set of a minimum decompositions of P_{ij} as viewed from each member of KER. if j-i = 2, P_{ij} will consists of a single triangle. Points in KER that lie in the triangle have real minimum decompositions of P_{ij}. Points in KER that do not lie in the triangle but are visible from v_{i}, v_{i+1}, andv_{j}

have pseudo minimum decompositions of P_{ij}. Otherwise for each base triangle T_{imj} of P_{ij} for each point x ∈ KER:

(a) If both MD_{x} of P_{im} and MD′_{x} of P_{mj} exist then they are merged to form a candidate M_{x} of P_{ij}.

(b) If x is visible from v_{j}, then the MD_{x} of P_{im} single merges with T_{imj}.

To form the new MD_{x} of P_{ij}, the MD_{x} of P_{im}, T_{imj} and the small-