Approximate guarding of monotone and rectilinear polygons

DOI10.1007/s00453-012-9653-3zbMath1267.68274OpenAlexW2059897834WikidataQ56700064 ScholiaQ56700064MaRDI QIDQ2375947

Erik A. Krohn, Bengt J. Nilsson

Publication date: 25 June 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2043/15471

zbMATH Keywords

computational geometryapproximation algorithmsart gallery problemsrectilinear polygonsmonotone polygons

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (12)

Guarding monotone art galleries with sliding cameras in linear time ⋮ Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ The VC-dimension of visibility on the boundary of monotone polygons ⋮ On orthogonally guarding orthogonal polygons with bounded treewidth ⋮ A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras ⋮ On vertex guarding staircase polygons ⋮ On the complexity of half-guarding monotone polygons ⋮ The parameterized complexity of guarding almost convex polygons ⋮ On Guarding Orthogonal Polygons with Sliding Cameras ⋮ Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation ⋮ Unnamed Item ⋮ A constant-factor approximation algorithm for vertex guarding a WV-polygon

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rectilinear link distance
• Guarding galleries and terrains
• Corrections to Lee's visibility polygon algorithm
• Optimum watchman routes
• A short proof of Chvatal's Watchman Theorem
• A combinatorial theorem in plane geometry
• Visibility of a simple polygon
• A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
• Computational complexity of art gallery problems
• A linear algorithm for computing the visibility polygon from a point
• Illumination of convex discs
• An Optimal Algorithm for Finding the Kernel of a Polygon
• Improved approximation algorithms for geometric set cover
• On Guarding Rectilinear Domains

This page was built for publication: Approximate guarding of monotone and rectilinear polygons