Note on covering monotone orthogonal polygons with star-shaped polygons. (English) Zbl 1187.68644
Inf. Process. Lett. 104, No. 6, 220-227 (2007); corrigendum ibid. 114, No. 11, 646-654 (2014).
Summary: In 1986, Keil provided an \(O(n^{2})\) time algorithm for the problem of covering monotone orthogonal polygons with the minimum number of \(r\)-star-shaped orthogonal polygons. This was later improved to \(O(n)\) time and space by L. Gewali, M. Keil and S. Ntafos [Inf. Sci. 65, No. 1–2, 45–63 (1992; Zbl 0792.68187)]. In this paper we simplify the latter algorithm – we show that with a little modification, the first step Sweep1 of the discussed algorithm – which computes the top ceilings of horizontal grid segments – can be omitted. In addition, for the minimum orthogonal guard problem in the considered class of polygons, our approach provides a linear time algorithm which uses \(O(k)\) additional space, where \(k\) is the size of the optimal solution – the algorithm in [loc. cit.] uses both \(O(n)\) time and \(O(n)\) additional space.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 52B55 | Computational aspects related to convexity |
Citations:
Zbl 0792.68187References:
| [1] | A. Aggarwal, The art gallery theorem: its variations, applications, and algorithmic aspects, PhD thesis, Johns Hopkins University, 1984; A. Aggarwal, The art gallery theorem: its variations, applications, and algorithmic aspects, PhD thesis, Johns Hopkins University, 1984 |
| [2] | B.M. Chazelle, D. Dobkin, Decomposing a polygon into convex parts, in: Proc. 11th ACM Symposium on the Theory of Computing, 1979, pp. 38-48; B.M. Chazelle, D. Dobkin, Decomposing a polygon into convex parts, in: Proc. 11th ACM Symposium on the Theory of Computing, 1979, pp. 38-48 |
| [3] | J.C. Culberson, R.A. Reckhow, A unified approach to orthogonal polygon covering problems via dent diagrams, Technical Report TR 89-06, University of Alberta, 1989; J.C. Culberson, R.A. Reckhow, A unified approach to orthogonal polygon covering problems via dent diagrams, Technical Report TR 89-06, University of Alberta, 1989 · Zbl 0684.68051 |
| [4] | Culberson, J. C.; Reckhow, R. A., Covering polygons is hard, Journal of Algorithms, 17, 1, 2-44 (1994) · Zbl 0811.68089 |
| [5] | D.S. Franzblau, D.J. Kleitman, An algorithm for constructing regions with rectangles: Independence and minimum generating sets for collections of intervals, in: Proc. 16th ACM Symposium on the Theory of Computing, 1984, pp. 167-174; D.S. Franzblau, D.J. Kleitman, An algorithm for constructing regions with rectangles: Independence and minimum generating sets for collections of intervals, in: Proc. 16th ACM Symposium on the Theory of Computing, 1984, pp. 167-174 |
| [6] | Gewali, L.; Keil, M.; Ntafos, S. C., On covering orthogonal polygons with star-shaped polygons, Information Sciences, 65, 45-63 (1992) · Zbl 0792.68187 |
| [7] | J.M. Keil, Minimally covering a horizontally convex orthogonal polygon, in: Proc. 2nd Annual Symposium on Computational Geometry, 1986, pp. 43-51; J.M. Keil, Minimally covering a horizontally convex orthogonal polygon, in: Proc. 2nd Annual Symposium on Computational Geometry, 1986, pp. 43-51 |
| [8] | Keil, J. M., Polygon decomposition, (Handbook of Computational Geometry (2000), North-Holland Publishing: North-Holland Publishing Amsterdam), 491-518 · Zbl 0948.68189 |
| [9] | Keil, J. M.; Sack, J.-R., Minimum decomposition of polygonal objects, (Computational Geometry (1985), North-Holland: North-Holland Amsterdam), 197-216 |
| [10] | A. Lubiw, Orderings and some combinatorial optimization problems with geometric applications, PhD thesis, University of Toronto, 1986; A. Lubiw, Orderings and some combinatorial optimization problems with geometric applications, PhD thesis, University of Toronto, 1986 |
| [11] | Motwani, R.; Raghunathan, A.; Saran, H., Perfect graphs and orthogonally convex covers, SIAM Journal on Discrete Mathematics, 2, 371-392 (1989) · Zbl 0674.05070 |
| [12] | Motwani, R.; Raghunathan, A.; Saran, H., Covering orthogonal polygons with star polygons: the perfect graph approach, J. Computer and System Sciences, 40, 19-48 (1990) · Zbl 0705.68082 |
| [13] | A. Raghunathan, Polygon Decomposition and perfect graphs, PhD thesis, University of California, 1988; A. Raghunathan, Polygon Decomposition and perfect graphs, PhD thesis, University of California, 1988 |
| [14] | R.A. Reckhow, Covering orthogonally convex polygons with three orientations of dents, Technical Report TR 87-17, University of Alberta, 1987; R.A. Reckhow, Covering orthogonally convex polygons with three orientations of dents, Technical Report TR 87-17, University of Alberta, 1987 |
| [15] | O’Rourke, J.; Supowit, K. J., Some NP-hard polygon decomposition problems, IEEE Transactions on Information Theory, 29, 2, 181-189 (1983) · Zbl 0501.68036 |
| [16] | O’Rourke, J., Visibility, (Handbook of Discrete and Computational Geometry (2004), CRC Press), 643-664 · Zbl 1056.52001 |
| [17] | Preparata, F. P.; Shamos, M. I., Computational Geometry (1985), Springer-Verlag: Springer-Verlag New York · Zbl 0759.68037 |
| [18] | Urrutia, J., Art gallery and illumination problems, (Handbook on Computational Geometry (2000), Elsevier Science: Elsevier Science Amsterdam), 973-1027 · Zbl 0941.68138 |
| [19] | Ch. Worman, Decomposing polygons into \(r Α; \); Ch. Worman, Decomposing polygons into \(r Α; \) |
| [20] | Worman, Ch.; Keil, J. M., Polygon decomposition and the orthogonal art gallery problem, International Journal of Computational Geometry and Applications, 17, 2, 105-138 (2007) · Zbl 1144.65015 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
