2021/02/20 by Sharareh Alipour, Alipour, Sharareh
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2102.10317
openalex publication_date 2021/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
There is an old conjecture by Shermer \citesher that in a polygon with n vertices and h holes, \lfloor \dfracn+h3 \rfloor vertex guards are sufficient to guard the entire polygon. The conjecture is proved for h=1 by Shermer \citesher and Aggarwal \citeaga seperately. In this paper, we prove a theorem similar to the Shermer's conjecture for a special case where the goal is to guard the vertices of the polygon (not the entire polygon) which is equivalent to finding a dominating set for the visibility graph of the polygon. Our proof also guarantees that the selected vertex guards also cover the entire outer boundary (outer perimeter of the polygon) as well.