LINEAR-TIME 3-APPROXIMATION ALGORITHM FOR THE r-STAR COVERING PROBLEM
Publication:4650093
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
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 (3)
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
This page was built for publication: LINEAR-TIME 3-APPROXIMATION ALGORITHM FOR THE r-STAR COVERING PROBLEM