2025/10/29 by Bahoo, Yeganeh, Kamaludeen, Ahmad
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2510.25567
We explore the problem of M-guarding polygons with holes using k-visibility guards, where a set of guards is said to M-guard a polygon if every point in the polygon is visible to at least M guards, with the constraint that there may only be 1 guard on each edge. A k-visibility guard can see through up to k walls, with k ≥ 2. We present a theorem establishing that any polygon with holes can be 2-guarded under k-visibility where k ≥ 2, which expands existing results in 0-visibility. We provide an algorithm that M-guards a polygon using a convex decomposition of the polygon. We show that every point in the polygon is visible to at least four 2-visibility guards and then extend the result to show that for any even k ≥ 2 there exists a placement of guards such that every point in the polygon is visible to k + 2 guards.