Covering Orthogonal Polygons with Star Polygons: The Perfect Graph Approach

Rajeev Motwani, Arvind Raghunathan and Huzur Saran

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-87-384
December 1987

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-384.pdf

We consider the problem of covering simple orthogonal polygons with star polygons. A star polygon contains a point p, such that for every point q in the star polygon, there is an orthogonally convex polygon containing p and q.

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 contained together in a covering star polygon. Further, the Ellipsoid method gives us a polynomial algorithm for this covering problem.

In the case where the polygon has at most three dent orientations, we show that the polygon covering problem can be reduced to the problem of covering a triangulated (chordal) graph with a minimum number of cliques. This gives us an O(n^3) algorithm.


BibTeX citation:

@techreport{Motwani:CSD-87-384,
    Author = {Motwani, Rajeev and Raghunathan, Arvind and Saran, Huzur},
    Title = {Covering Orthogonal Polygons with Star Polygons: The Perfect Graph Approach},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1987},
    Month = {Dec},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/6218.html},
    Number = {UCB/CSD-87-384},
    Abstract = {We consider the problem of covering simple orthogonal polygons with star polygons. A star polygon contains a point <i>p</i>, such that for every point <i>q</i> in the star polygon, there is an orthogonally convex polygon containing <i>p</i> and <i>q</i>.   <p>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 <i>P</i> without holes is equal to the maximum number of points of <i>P</i>, no two of which can be contained together in a covering star polygon. Further, the Ellipsoid method gives us a polynomial algorithm for this covering problem.   <p>In the case where the polygon has at most three dent orientations, we show that the polygon covering problem can be reduced to the problem of covering a triangulated (chordal) graph with a minimum number of cliques. This gives us an <i>O</i>(<i>n</i>^3) algorithm.}
}

EndNote citation:

%0 Report
%A Motwani, Rajeev
%A Raghunathan, Arvind
%A Saran, Huzur
%T Covering Orthogonal Polygons with Star Polygons: The Perfect Graph Approach
%I EECS Department, University of California, Berkeley
%D 1987
%@ UCB/CSD-87-384
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/6218.html
%F Motwani:CSD-87-384