ISBN:  Unavailable

Category: Unavailable

Page count: 30

In general, orthogonal polygons can have concavities (dents) with four possible orientations. In this case, we show that the polygon covering problem can be reduced to the problem of covering a weakly triangulated graph with a minimum number of cliques. Since weakly triangulated graphs are perfect, we obtain the following duality relationship: the minimum number of star polygons needed to cover an orthogonal polygon P without holes is equal to the maximum number of points of P, no two of which can be con tained together in a covering star polygon. Further, the Ellipsoid method gives us a polynomial algorithm for this covering problem.