LINEAR-TIME 3-APPROXIMATION ALGORITHM FOR THE r-STAR COVERING PROBLEM

DOI10.1142/S021819591250001XzbMath1251.68288OpenAlexW1979511537MaRDI 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

zbMATH Keywords

approximation algorithmsorthogonal polygon\(r\)-star cover

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

On orthogonally guarding orthogonal polygons with bounded treewidth ⋮ Minimum r-Star Cover of Class-3 Orthogonal Polygons ⋮ Mobile versus point guards

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