Covering orthogonal polygons with star polygons: The perfect graph approach. (English) Zbl 0705.68082

Motwani, Rajeev; Raghunathan, Arvind; Saran, Huzur

J. Comput. Syst. Sci. 40, No. 1, 19-48 (1990).

Summary: This paper studies the combinatorial structure of visibility in orthogonal polygons. We show that the visibility graph for the problem of minimally covering simple orthogonal polygons with star polygons is perfect. 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. This perfectness property implies a polynomial algorithm for the above polygon covering problem. It further provides us with an interesting duality relationship. We first establish that a minimum clique cover of the visibility graph of a simple orthogonal polygon corresponds exactly to a minimum star cover of the polygon. In general, simple orthogonal polygons can have concavities (dents) with four possible orientations. We show that the visibility graph is weakly triangulated. We thus obtain an \(O(n^ 8)\) algorithm. Since weakly triangulated graphs are perfect, we also obtain an interesting duality relationship. In the case where the polygon has at most three dent orientations, we show that the visibility graph is triangulated or chordal. This gives us an \(O(n^ 3)\) algorithm.

MSC:

68R10	Graph theory (including graph drawing) in computer science
68U05	Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25	Analysis of algorithms and problem complexity

Keywords:

star polygons; perfect graph; combinatorial structure of visibility; orthogonal polygons; polygon covering problem

References:

[1]	Aggarwal, A., The art gallery theorem: its variations, applications and algorithmic aspects, ()
[2]	Albertson, M.; O’Keefe, C., Covering regions with squares, SIAM J. algebraic discrete methods, 2, 240-243, (1981) · Zbl 0498.05054
[3]	Boucher, A., It’s hard to color antirectangles, SIAM J. algebraic discrete methods, 5, (1984) · Zbl 0542.05027
[4]	Chaiken, S.; Kleitman, D.J.; Saks, M.; Shearer, J., Covering regions by rectangles, SIAM J. algebraic discrete methods, 2, 394-410, (1981) · Zbl 0506.05022
[5]	Chazelle, B.; Dobkin, D., Decomposing a polygon into its convex parts, (), 38-48
[6]	Chazelle, B., Computational geometry and convexity, ()
[7]	Culberson, J.; Reckhow, R., Dent diagrams: A unified approach to polygon covering problems, ()
[8]	Culberson, J.; Reckhow, R., Covering polygons is hard, () · Zbl 0811.68089
[9]	Edelsbrunner, H., Algorithms in combinatorial geometry, () · Zbl 0634.52001
[10]	Franzblau, D.S.; Kleitman, D.J., An algorithm for constructing regions with rectangles independence and minimum generating sets for collection of intervals, (), 167-174
[11]	Gavril, F., Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph, SIAM J. comput., 1, 180-187, (1972) · Zbl 0227.05116
[12]	Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[13]	{\scE. Gyóri}, A minimax theorem of new type, to appear.
[14]	Hayward, R.B., Weakly triangulated graphs, J. conibin. theory ser. B, 39, 200-209, (1985) · Zbl 0551.05055
[15]	Keil, J.M.; Sack, J.R., Minimum decompositions of polygonal objects, ()
[16]	Keil, J.M., Decomposing a polygon into simpler components, SIAM J. comput., 14, 799-817, (1985) · Zbl 0575.68077
[17]	Keil, J.M., Minimally covering a horizontally convex orthogonal polygon, (), 43-51
[18]	Lovász, L., Perfect graphs, (), 55-85
[19]	Molnar, J., Über den zweidimensionalen topologischen satz von Helly, Mat. lapok, 8, 108-114, (1957), [Hungarian with German and Russian summaries] · Zbl 0105.16705
[20]	Motwani, R.; Raghunathan, A.; Saran, H., Perfect graphs and orthogonally convex covers, SIAM J. discrete math., 14, (1989) · Zbl 0674.05070
[21]	O’Rourke, J., Art gallery theorems and algorithms, (1987), Oxford University Press New York · Zbl 0653.52001
[22]	A. RAGHUNATHAN, Algorithms for weakly triangulated graphs, J. Algorithms, in press.
[23]	Reckhow, R.; Culberson, J., Covering a simple orthogonal polygon with a minimum number of orthogonally convex polygons, (), 268-277
[24]	Reckhow, R., Covering orthogonally convex polygons with three orientations of dents, ()
[25]	Rose, A.; Tarjan, R.; Lueker, G., Algorithmic aspects of vertex elimination on graphs, SIAM J. comput., 5, 266-283, (1976) · Zbl 0353.65019
[26]	Saks, M., A class of perfect graphs associated with planar rectilinear regions, SIAM J. algebraic discrete methods, 3, 330-342, (1982) · Zbl 0506.05050
[27]	Shearer, J.B., A class of perfect graphs, SIAM J. algebraic discrete methods, 3, 281-284, (1982) · Zbl 0506.05049
[28]	O’Rourke, J.; Supowit, K., Some NP-hard polygon decompositions problems, IEEE trans. inform. theory, IT-29, No. 2, 181-190, (1983) · Zbl 0501.68036