Minimum \(r\)-star cover of class-3 orthogonal polygons. (English) Zbl 1401.68351
Kratochvíl, Jan (ed.) et al., Combinatorial algorithms. 25th international workshop, IWOCA 2014, Duluth, MN, USA, October 15–17, 2014. Revised selected papers. Cham: Springer (ISBN 978-3-319-19314-4/pbk; 978-3-319-19315-1/ebook). Lecture Notes in Computer Science 8986, 286-297 (2015).
Summary: We are interested in the problem of covering simple orthogonal polygons with the minimum number of \(r\)-stars; an orthogonal polygon is an \(r\)-star if it is star-shaped. The problem has been considered by C. Worman and J. M. Keil [Int. J. Comput. Geom. Appl. 17, No. 2, 105–138 (2007; Zbl 1144.65015)] who described an algorithm running in \(O(n^{17} \text{poly-log}\, n)\) time where \(n\) is the size of the input polygon.{
}
In this paper, we consider the above problem on simple class-3 orthogonal polygons, i.e., orthogonal polygons that have dents along at most 3 different orientations. By taking advantage of geometric properties of these polygons, we give an output-sensitive \(O(n + k \log k)\)-time algorithm where \(k\) is the size of a minimum \(r\)-star cover; this is the first purely geometric algorithm for this problem. Ideas in this algorithm may be generalized to yield faster algorithms for the problem on general simple orthogonal polygons.
For the entire collection see [Zbl 1318.68027].
For the entire collection see [Zbl 1318.68027].
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Citations:
Zbl 1144.65015References:
| [1] | Aggarwal, A.: The art gallery theorem: its variations, applications, and algorithmic aspects. Ph.D. thesis, Department of Electrical Engineering and Computer Science, Johns Hopkins University (1984) |
| [2] | Culberson, J.; Reckhow, RA, Orthogonally convex coverings of orthogonal polygons without holes, J. Comput. Syst. Sci., 39, 2, 166-204 (1989) · Zbl 0684.68051 · doi:10.1016/0022-0000(89)90043-3 |
| [3] | Hertel, S., Mehlhorn, K.: Fast triangulation of simple polygons. In: FCT 1983: Proceedings of the 4th International Conference on Fundamentals of Computation Theory, pp. 207-218 (1983) · Zbl 0521.68040 |
| [4] | Gewali, L.; Keil, M.; Ntafos, SC, On covering orthogonal polygons with star-shaped polygons, Inf. Sci., 65, 45-63 (1992) · Zbl 0792.68187 · doi:10.1016/0020-0255(92)90077-L |
| [5] | Kahn, J.; Klawe, M.; Kleitman, D., Traditional galleries require fewer watchmen, SIAM J. Algebraic Discrete Methods, 4, 2, 194-206 (1983) · Zbl 0533.05021 · doi:10.1137/0604020 |
| [6] | Keil, JM, Decomposing a polygon into simpler components, SIAM J. Comput., 14, 799-817 (1985) · Zbl 0575.68077 · doi:10.1137/0214056 |
| [7] | Keil, J.M.: Minimally covering a horizontally convex orthogonal polygon. In: SoCG 1986: Proceedings of the 2nd Annual ACM Symposium Computational Geometry, pp. 43-51 (1986) |
| [8] | Li, G., Zhang, H.: A rectangular partition algorithm for planar self-assembly. In: IROS 2005: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3213-3218 (2005) |
| [9] | Lingas, A.; Palios, L.; Wasylewicz, A.; Żyliński, P., Corrigendum: note on covering orthogonal polygons, Inf. Process. Lett., 114, 646-654 (2014) · Zbl 1293.68296 · doi:10.1016/j.ipl.2014.03.016 |
| [10] | Lingas, A.; Wasylewicz, A.; Żyliński, P., Note on covering orthogonal polygons with star-shaped polygons, Inf. Process. Lett., 104, 6, 220-227 (2007) · Zbl 1187.68644 · doi:10.1016/j.ipl.2007.06.015 |
| [11] | Lingas, A.; Wasylewicz, A.; Żyliński, P., Linear-time 3-approximation algorithm for the \(r\)-star covering problem, Int. J. Comput. Geom. Appl., 22, 2, 103-141 (2012) · Zbl 1251.68288 · doi:10.1142/S021819591250001X |
| [12] | Motwani, R.; Raghunathan, A.; Saran, H., Covering orthogonal polygons with star polygons: the perfect graph approach, J. Comput. Syst. Sci., 40, 19-48 (1990) · Zbl 0705.68082 · doi:10.1016/0022-0000(90)90017-F |
| [13] | Worman, C.; Keil, JM, Polygon decomposition and the orthogonal art gallery problem, Int. J. Comput. Geom. Appl., 17, 2, 105-138 (2007) · Zbl 1144.65015 · doi:10.1142/S0218195907002264 |
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.
