Rajeev Motwani and Arvind Raghunathan and Huzur Saran

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-87-384

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

---

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