ART GALLERY PROBLEMS

Problem(Klee)

Imagine an art gallery room whose floor plan can 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.

• Points(Steiner) guards are more powerful then vertex guards and harder to find.

• Partition pieces are not allowed to overlap.

• Cover overlapping is permitted.

The Minimal Guard Coverage Problem has four input components

• Decomposition Type

• Shape of Component Pieces

• Guard’s Place

• Polygon Restrictions

Applications

• An arbitrary polygonal shape can be recognized more easily once its component parts have been identified.(Pattern Recognition) We can solve the problems from bottom-up fashion by solving the components and get the global solution. Since the components will be uniform, we can apply special algorithms for these components.

• Database systems

• Computer Graphics 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.

KEIL’S ALGORITHM

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}.

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}, and v_{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 smallest MD of P_{mj} are combined.

(c) if x lies in T_{imj} or x is visible from v_{i}, v_{m} and v_{j} through edge v_{i}v_{j}, then x is the candidate for MD_{x} of P_{ij}. This candidate is formed by taking the smallest real minimum decomposition of P_{im} together with T_{imj} and the smallest real MD of P_{im}.

As the various candidates for the MD_{x} of P_{ij} are considered only the smallest is kept. Also the smallest real MD of P_{ij} will be needed when no merge past v_{i}v_{j} is performed.

3. Since the subpolygon P_{1n}=P, the smallest real minimum decomposion of P_{1n} is kept as a minimum star-shaped decomposition of P.

Analysis

Let n denote the number of vertices in the polygon P and N denote the number of notches in the polygon.

• Dynamic Programming parts dominates the total complexity of the algorithm.

• The test at 2.a, 2.b and 2.c can be done in O(log n).

• There are O(n^{2}N^{2}) points in KER so that O(n^{2}N^{2} log n) time is spend for each base triangle T_{imj}.

• The total complexity of the algorithm is O(n^{5}N^{2} log n) because there are O(n^{3}) base triangles.

PARALLEL IMPLEMENTATION

• Each processor can calculate the minimum decomposition at P_{ij}. Assume that we have n processors for n element polygon P, then for(k=1;k<n-2;k++) calculate P_{(i−k−1)i} at processor i. At step k, each processor examines at most k base triangles for O(n^{2}N^{2}) points. Then the total complexity of this algorithm will be = O(n^{4}N^{2} log n)

• Distribute the total points O(n^{2}N^{2}) into n processors and let them find the minimum possible decomposition for the P_{ij} and apply cube collapse (to find the MD) for the entry P_{ij}. Since each processor will examine O(nN^{2}) points, it will take O(nN^{2} log n · n^{3}) time to find the minimum decomposition for each group of points. Then we need to add O(log n) time to find the global minimum decomposition of P_{ij} for each element of DP matrix. The total coplexity will be O(n^{4}N^{2} log n).

• Assume that we have O(n^{4}) processors then how we can calculate the matrix P.

a Assign each processor a point from KER so that every processor has

either one or no point assign to itself. b For each entry of matrix P, we broadcast the appropriate triangle infor-

mation to all processors(O(log n)) and each processor do the necessary calculation for its point.(O(log n)) Then we need to find out minimum value from these points then we apply the cube collapse algorithm to figure out the minimum value.(O(log n))

The complexity of the algorithm is dominated by the step b. In step b, we should do this calculation for every entry(O(n^{2})) and for each possible triangle(O(n)) so that the total complexity will be O(n^{3} · log n)

• Assume that we have n^{5} processor and each n^{4} processor group calculates O(n^{4}) points for prespecified triangle then the matrix P can be calculated as

a. Assign each processor a point from KER and one Triangle so that

every processor has either both or none information. b. For each entry of matrix P we broadcast the necessary information to

inform which processors will do the calculation and these processors do their pointTriangle pair calculation and the minimum result can be obtained with cube collapse.

The complexity of this algorithm will be O(n^{2} · log n)

• Can we do this calculation with n^{7} processors?. Let n^{2} processors hold the matrix P. Assume that we want to calculate the first diagonal, second diagonal,..etc. To calculate the entry at P_{i,j} where j − i > 2, we need to calculate values for triangles such as P_{i,(i+1)} and P_{i+1,j}, P_{i,(i+2)} and P_{i+2,j}, etc. The necessary values are not on the same diagonal then we can not apply pipelining on evaluations of the diagonal values.