The problem of finding the minimum r-star cover of orthogonal polygons had been open for many years, until 2004 when Ch. Worman and J. M. Keil proved it to be polynomial tractable (Polygon decomposition and the orthogonal art gallery problem, IJCGA 17(2) (2007), 105-138). However, their algorithm is not practical as it has O{top}~(n{sup}17) time complexity, where O{top}~() hides a polylogarithmic factor. Herein, we present a linear-time 3-approximation algorithm based upon the novel partition of a polygon into so-called [w]-star-shaped orthogonal polygons.
展开▼
