Note on covering monotone orthogonal polygons with star-shaped polygons

详细信息	查看全文 | 推荐本文 |

• 作者：Andrzej Lingas ; Agnieszka Wasylewicz ; Paweł ; Ż ; yliń ; ski
• 关键词：Computational geometry ; Covering polygons ; Orthogonal polygon
• 刊名：Information Processing Letters
• 出版年：2007
• 期刊代码：61_00200190
• 类别：cp
• 出版时间：16 December 2007
• 卷：104
• 期：6
• 页码：220-227
• 文件大小：209 K

摘要

In 1986, Keil provided an O(n²) 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 Gewali et al. in [L. Gewali, M. Keil, S.C. Ntafos, On covering orthogonal polygons with star-shaped polygons, Information Sciences 65 (1992) 45–63]. 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 [L. Gewali, M. Keil, S.C. Ntafos, On covering orthogonal polygons with star-shaped polygons, Information Sciences 65 (1992) 45–63] uses both O(n) time and O(n) additional space.