On the complexity of half-guarding monotone polygons

DOI10.1007/978-3-031-20624-5_46arXiv2204.13143OpenAlexW4312354681MaRDI QIDQ6164016

Hannah Miller Hillberg, Alex Pahlow, Erik A. Krohn

Publication date: 26 July 2023

Published in: LATIN 2022: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2204.13143

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Improved approximations for guarding 1.5-dimensional terrains
• On recognizing and characterizing visibility graphs of simple polygons
• Guarding galleries and terrains
• Illumination of polygons with vertex lights
• Allocating vertex \(\pi\)-guards in simple polygons via pseudo-triangulations
• Approximability of guarding weak visibility polygons
• Approximate guarding of monotone and rectilinear polygons
• Terrain Guarding is NP-Hard
• Computational complexity of art gallery problems
• The Floodlight Problem
• Illumination of Orthogonal Polygons with Orthogonal Floodlights
• Vertex Guarding in Weak Visibility Polygons
• Orthogonal Terrain Guarding is NP-complete
• Art galleries with guards of uniform range of vision

This page was built for publication: On the complexity of half-guarding monotone polygons