LINEAR-TIME 3-APPROXIMATION ALGORITHM FOR THE r-STAR COVERING PROBLEM
From MaRDI portal
Publication:4650093
DOI10.1142/S021819591250001XzbMath1251.68288MaRDI QIDQ4650093
Agnieszka Wasylewicz, Paweł Żyliński, Andrzej Lingas
Publication date: 23 November 2012
Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s021819591250001x
52B55: Computational aspects related to convexity
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
Mobile versus point guards, On orthogonally guarding orthogonal polygons with bounded treewidth, Minimum r-Star Cover of Class-3 Orthogonal Polygons
Cites Work
- Covering orthogonal polygons with star polygons: The perfect graph approach
- On covering orthogonal polygons with star-shaped polygons
- POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM
- Perfect Graphs and Orthogonally Convex Covers
- Some NP-hard polygon decomposition problems
- Covering Polygons Is Hard