Connecting guards with minimum Steiner points inside simple polygons

DOI10.1016/J.TCS.2018.12.008MaRDI QIDQ2419109zbMATH OpenOpenAlexFDO

Authors A. Ahadi, Alireza Zarei

Publication date 29 May 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2018.12.008

zbMATH Keywords

art gallery problemconnected guard setNP-hardnessSteiner guardsSteiner tree problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Approximability of guarding weak visibility polygons
• Guarding galleries and terrains
• Vertex guarding in weak visibility polygons
• THE MINIMUM GUARDING TREE PROBLEM
• An approximation algorithm for the art gallery problem

Cites work

• An improved LP-based approximation for Steiner tree
• Computational complexity of art gallery problems
• Hard tiling problems with simple tiles
• Hiding people in polygons
• scientific article; zbMATH DE number 3520315 (Why is no real title available?)
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Visibility Algorithms in the Plane

Cited in

(2)

• Guarding a Polygon Without Losing Touch
• Approximation algorithms for the freeze tag problem inside polygons

This page was built for publication: Connecting guards with minimum Steiner points inside simple polygons

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