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

DOI10.1007/978-3-540-77891-2_15MaRDI QIDQ5452162zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Linear-time 3-approximation algorithm for the \(r\)-star covering problem
• Minimum \(r\)-star cover of class-3 orthogonal polygons
• Note on covering monotone orthogonal polygons with star-shaped polygons
• On covering orthogonal polygons with star-shaped polygons
• Covering orthogonal polygons with star polygons: The perfect graph approach

Cites work

• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 1424299 (Why is no real title available?)
• Covering Polygons Is Hard
• Covering orthogonal polygons with star polygons: The perfect graph approach
• Decomposing a Polygon into Simpler Components
• Note on covering monotone orthogonal polygons with star-shaped polygons
• OPTIMUM GUARD COVERS AND m-WATCHMEN ROUTES FOR RESTRICTED POLYGONS
• On covering orthogonal polygons with star-shaped polygons
• Orthogonally convex covering of orthogonal polygons without holes
• POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM
• Perfect Graphs and Orthogonally Convex Covers
• Semidefinite programming and integer programming
• Some NP-hard polygon decomposition problems
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(5)

• Minimum \(r\)-star cover of class-3 orthogonal polygons
• Guarding orthogonal art galleries with sliding cameras
• Linear-time 3-approximation algorithm for the \(r\)-star covering problem
• Note on covering monotone orthogonal polygons with star-shaped polygons
• scientific article; zbMATH DE number 7758359 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5452162)