Linear-Time 3-Approximation Algorithm for the r-Star Covering Problem

DOI10.1007/978-3-540-77891-2_15zbMath1132.68821OpenAlexW1849516636MaRDI QIDQ5452162

Agnieszka Wasylewicz, Paweł Żyliński, Andrzej Lingas

Publication date: 25 March 2008

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77891-2_15

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (1)

Guarding orthogonal art galleries with sliding cameras

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Covering orthogonal polygons with star polygons: The perfect graph approach
• The ellipsoid method and its consequences in combinatorial optimization
• On covering orthogonal polygons with star-shaped polygons
• Orthogonally convex covering of orthogonal polygons without holes
• Note on covering monotone orthogonal polygons with star-shaped polygons
• POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM
• Decomposing a Polygon into Simpler Components
• Perfect Graphs and Orthogonally Convex Covers
• Some NP-hard polygon decomposition problems
• Covering Polygons Is Hard
• OPTIMUM GUARD COVERS AND m-WATCHMEN ROUTES FOR RESTRICTED POLYGONS

This page was built for publication: Linear-Time 3-Approximation Algorithm for the r-Star Covering Problem