ART GALLERY PROBLEMS

INTRODUCTION 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. What is visibility ( or visible)? A point x can see point y (or y is visible from x) iff the closed segment \overline{xy} is nowhere

exterior to the polygon P : \overline{xy} ⊆ P. This definition permits the line-of-sight to have grazing contact with a vertex.

x has clear visibility to y if \overline{xy} ⊆ P and \overline{xy} ∩ ∂P ⊆ x, y

Figure 1: Visibility

A set of guards is said to cover a polygon if every point in the polygon is visible to some guard. Guards themselves do not block each others visibility.

The guards can see only points of ∂P.(Optional) Klee’s question seeks Express as a function of n, the smallest number of guards that suffice to cover any

polygon of n vertices.

necessary - at least that many are needed for some polygon. sufficent - that many always suffice for any polygon.

Sufficiency Measures

one guard is always necessary

n guard is the upper limit ( place one guard for each vertex)

Necessary Measures

one guard(convex n-gons)

Figure 2: Figure 3: Figure 4:

⌊\frac{n}{3}⌋ guard

Fisk’s Proof : . Triangulate with diagonals . Apply 3 Coloring . Put guards one specific color . According to pigeon hole principle we need ⌊\frac{n}{3}⌋ guards.

Is a guard on every third vertex is sufficient?

Figure 5:

If we put guards all the vertices i with i ≡ m(mod3) obviously we can not cover one of x_{0}, x_{1} or x_{2}.

The Visibility of Interior is different from the Visibility of the boundary.

Figure 6:

Guards are placed such that they can see all the paintings on the walls ≠> guards see the interior.

Guard Types

Vertex Guards (without Steiner Points) a guard can be located only a vertex.

Point Guards (with Steiner Points) no restriction on their location as long as they are inside of the polygon or on the polygon boundary.

Figure 7:

Points guards are more powerful then vertex guards.

Partition pieces are not allowed to overlap. Cover overlapping is permitted.

The Minimal Guard Coverage Problem has four input components

• Decomposition Type Partition/Cover Covers can be significantly more efficient then partitions.

• Shape of Component Pieces Convex, Star, Spinal, Monotone, Trapezoidal,..

• Guard’s Place (Steiner or not)

Figure 8:

Steiner points are more efficient and harder to find. A minimum convex partition without Steiner points has no more than four times the number of pieces in a minimal partition with steiner points. We don not have the above result for Star pieces.

• Polygon Restrictions (with or without Holes)

Convex partitions with Steiner points no hole (polynomial time) Convex partitions with Steiner points with hole(s) (NP-hard) Star cover with holes without Steiner points is NP-hard. Finding a minimal star cover with Steiner points without holes is NP-hard, also.

Which type of applications do we have for Polygon Decomposition?

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 and graphics are the other application areas.

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.

I summarize the some information from the Keil’s paper[1] in the following part.

1. DEFINITIONS

Definition 1 : If the interior angle at a vertex is greter than 180(reflex) the vertex is called notch.

Definition 2 : Let P be a polygon in the plane having vertices v_{1}, v_{2}, v_{3}, ⋯, v_{n} clockwise on its boundary. If a vertex x is a notch or v_{1} or v_{n}, then it is called reference vertex of P. A vertex x is called convex vertex if it is not a reference vertex.

Definition 3 : A Star-shaped Polygon is a polygon in which the entire polygon is visible from at least one fixed(possibly interior) point of the polygon.

Definition 4 : A pseudo star-shaped Polygon P S_{ij} of P based along v_{i}v_{j} has the property that there exists a point x in P and not in P S_{ij} so that every point of P S_{ij} can be seen from x through v_{i}v_{j}.

Definition 5 : Let P be a polygon in the plane having vertices v_{1}, v_{2}, v_{3}, ⋯, v_{n} clockwise on its boundary. A subpolygon is called a valid subpolygon when either i=1 or j=n or at least one of v_{i} and v_{j} is a notch. A valid subpolygon P_{ij}is divided into three class;

type a : if both v_{i} and v_{j} are reference vertices.

type b : if v_{i} is a reference vertex and v_{j} is convex vertex.

type b : if v_{i} is convex vertex and v_{j} is a reference vertex.

Definition 6 : Two points of a polygon P are said to be visible if the line segment joining them lies whooly inside P.

Definition 7 : Let P be a polygon in the plane having vertices v_{1}, v_{2}, v_{3}, ⋯, v_{n} clockwise on its boundary. A subpolygon P_{ij} of P with vertices v_{i}, v_{i+1}, ⋯, v_{j} exists when 1 ≤ i < j −1 ≤ n−1, and v_{i}v_{j} are visible.

Definition 8 : Let P be a polygon in the plane having vertices v_{1}, v_{2}, v_{3}, ⋯, v_{n} clockwise on its boundary. The base convex polygon C_{ij} of a minimum decomposition (MD) D of P_{ij} is that convex polygon of D that contains the edge v_{i}v_{j} in its boundary. v_{i}v_{j} is called base edge of P_{ij}.

Definition 9 : Let P be a polygon in the plane having vertices v_{1}, v_{2}, v_{3}, ⋯, v_{n} clockwise on its boundary. The base triangle T_{imj} of P_{ij} is a triangle v_{i}v_{m}v_{j} (i < m < j) where each of v_{i}v_{m} and v_{m}v_{j} is either a base edge of a valid subpolygon or an original side of P.

Definition 10 : Let P be a polygon in the plane having vertices v_{1}, v_{2}, v_{3}, ⋯, v_{n} clockwise on its boundary. The set of polygons from which the entire polygon P is visible is called the kernel of P.

Definition 11 : Let P be a polygon in the plane having vertices v_{1}, v_{2}, v_{3}, ⋯, v_{n} clockwise on its boundary. Let S_{im}(A) be the base star-shaped polygon of the minimum star-shaped decomposition A of P_{im}. A triangle T_{imj} can single-merge with a minimum decomposition A of P_{im} if S_{im}(A) ∪ T_{imj} is a star-shaped polygon.

Definition 12 : Let P be a polygon in the plane having vertices v_{1}, v_{2}, v_{3}, ⋯, v_{n} clockwise on its boundary. Let S_{im}(A) be th base star-shaped polygon of the minimum star-shaped decomposition A of P_{im}. A triangle T_{imj} can double-merge with a minimum decomposition A of P_{im} and a minumum decomposition B of P_{mj} if S_{im}(A) ∪ T_{imj} ∪ S_{mj}(B) is a star-shaped polygon.

Definition 13 : (KER- Potential Kernel Points) If v_{a} and v_{b} are vertices of polygon P then there may exist a segment of the line through v_{a} and v_{b}, that lies entirely within P, that contains v_{b} and exactly one other boundary point v_{c} of P so that v_{b} lies between v_{a} and v_{c}. This segment denoted by I_{ab} that is a segment drawn inside P beginning at v_{b}, in the direction away from v_{a}, until the boundary of P is reached. The set of segments L can be defined as L={I_{ab} | v_{b} is a notch and v_{a} is a vertex of P visible from v_{b}}. The segments in L may intersects with each other or with sides of P or both. The KER denote the set of all such intersections together with the vertices of P.

Figure 9:

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

2.3 Analysis

Let n denote the number of vertices in the polygon P and N denote the number of notches in the polygon. Since the Dynamic Programming part dominates the total complexity of the algorithm, its complexity will provide the appropriate upper limit for the 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.

2.4 How can we find the Base Triangles

1. Determine which vertices are notches in O(n) time.

2. For each reference vertex x of P determine the set of vertices of P visible from x. For convex vertices store the set of visible reference vertices. Denote such a visibility list sorted by angle about Figure 10: Figure 11: Figure 12: vertex x as V(x). All of this can be done in O(nN) time using the visibility polygon algorithm of El-Gindy and Avis. (A visiblility polygon from a point inside the polygon P can be mode in O(n) time. Since there are N notches, it takes O(nN) time to get the visibility polygon of each notch.)

3. Since each visibility pair v_{i}v_{j} (i < j) determined in step 2 is the base edge of a valid subpolygon these valid subpolygons can be sorted in ascending order by the size measured j − i (This denotes the number of vertices in the subpolygon - 1) in time O(nN log nN).

4. For each subpolygon P_{ij} form the set of base triangles. In the O(N^{2}) subpolygons of type a this can be done in O(n) time by computing T={(V_{i} ∪ {v_{i+1}}) ∩ (V_{j} ∪ {v_{j−1}})}. In the O(nN) subpolygons of type b or c this can be done in O(N log n) time by computing T using a binary search.

3. PARALLEL IMPLEMENTATION

In step 2 of Dynamic Programming part, minimum decomposition will be calculated for each element of KER. Also this calculation has to be done for each base triangle. One possibility to make the program parellel is to let each processor 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^{2}N^{2} log n) + 2 · O(n^{2}N^{2} log n) + 3 · O(n^{2}N^{2} log n) + ⋯ (n − 2) · O(n^{2}N^{2} log n)
= O(n^{2}N^{2} log n)(1 + 2 + 3 + ⋯ + (n − 2))

= O(n^{2}N^{2} log n)\frac{(n − 2) · (n − 1)}{2} = O(n^{2}N^{2} log n) · O(n^{2})

= O(n^{4}N^{2} log n)

The second one is to 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).

Let’s examine the second step in the algorithm because it helps us to understand the algorithm so that we can try to figure out other calculations we can do concurrently. For each entry of matrix P, we need to look at O(n^{4}) points for the corresponding number of triangles and try to figure out the one who gives us the minimum value. Let’s enumarate the diagonals of the upper matrix (assume that the main diagonal has 0, the next is 1, and so on) Then the calculations on each element of the matrix will be like the following

Diagonal Number Number of Elements Number of Triangles
2  (n-2)  1
3  (n-3)  2
4  (n-4)  3
⋮  ⋮  ⋮
(n-1)  2  (n-3)
n  1  (n-2)

We need to this calculations for O(N^{4}) points to find the smallest one for this entry. Then the total calculation cost can be written as

∑_{i=2}^{n−1} O(n^{4}) · (n − i) · (i − 1)

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 information 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

\underbrace{O(n^{2})}_{number of entries} · \underbrace{O(n)}_{number of triangles} · (  \underbrace{O(log n)}_{broadcasting triangle info} + \underbrace{O(log n)}_{calculation} + \underbrace{O(log n)}_{finding minimum})

O(n^{3}) · (O(log n)) = 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

\underbrace{O(n^{2})}_{number of entries} · ( \underbrace{O(log n)}_{broadcasting info} + \underbrace{O(log n)}_{calculation} + \underbrace{O(log n)}_{finding minimum})

O(n^{2}) · (O(log n)) = 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.

References

[1] Keil, J. Mark, ”Decomposing a Polygon into Simpler Components”, SIAM J. Computing, Vol. 14, No: 4, November 1985, pp 799-817

[2] O’rourke, Joseph, Art Gallery Theorems and Algorithms, Oxford Press,1987

[3] O’rourke, Joseph, Computational Geometry in C, Cambridge University Press, 1993