Linear-time 3-approximation algorithm for the r-star covering problem
(2012) In International Journal of Computational Geometry and Applications 22(2). p.103-141- Abstract
- The complexity status of the minimum r-star cover problem for orthogonal polygons had been open for many years, until 2004 when Ch. Worman and J. M. Keil proved it to be polynomially tractable (Polygon decomposition and the orthogonal art gallery problem, IJCGA 17(2) (2007), 105-138). However, since their algorithm has (O) over tilde (n(17))-time complexity, where (O) over tilde (.) hides a polylogarithmic factor, and thus it is not practical, in this paper we present a linear-time 3-approximation algorithm. Our approach is based upon the novel partition of an orthogonal polygon into so-called o-star-shaped orthogonal polygons.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/3135836
- author
- Lingas, Andrzej LU ; Wasylewicz, Agnieszka and Zylinski, Pawel
- organization
- publishing date
- 2012
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Approximation algorithms, r-star cover, orthogonal polygon
- in
- International Journal of Computational Geometry and Applications
- volume
- 22
- issue
- 2
- pages
- 103 - 141
- publisher
- World Scientific Publishing
- external identifiers
-
- wos:000308706700001
- scopus:84866403378
- ISSN
- 0218-1959
- DOI
- 10.1142/S021819591250001X
- language
- English
- LU publication?
- yes
- id
- a4c9b8eb-ff52-41ec-a822-9c229d167634 (old id 3135836)
- date added to LUP
- 2016-04-01 14:45:11
- date last changed
- 2022-01-28 02:20:19
@article{a4c9b8eb-ff52-41ec-a822-9c229d167634, abstract = {{The complexity status of the minimum r-star cover problem for orthogonal polygons had been open for many years, until 2004 when Ch. Worman and J. M. Keil proved it to be polynomially tractable (Polygon decomposition and the orthogonal art gallery problem, IJCGA 17(2) (2007), 105-138). However, since their algorithm has (O) over tilde (n(17))-time complexity, where (O) over tilde (.) hides a polylogarithmic factor, and thus it is not practical, in this paper we present a linear-time 3-approximation algorithm. Our approach is based upon the novel partition of an orthogonal polygon into so-called o-star-shaped orthogonal polygons.}}, author = {{Lingas, Andrzej and Wasylewicz, Agnieszka and Zylinski, Pawel}}, issn = {{0218-1959}}, keywords = {{Approximation algorithms; r-star cover; orthogonal polygon}}, language = {{eng}}, number = {{2}}, pages = {{103--141}}, publisher = {{World Scientific Publishing}}, series = {{International Journal of Computational Geometry and Applications}}, title = {{Linear-time 3-approximation algorithm for the r-star covering problem}}, url = {{http://dx.doi.org/10.1142/S021819591250001X}}, doi = {{10.1142/S021819591250001X}}, volume = {{22}}, year = {{2012}}, }